目录
旋转数组
旋转数组找最小值
思路
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=100001;int n,num[N];
int bis(int a[],int left,int right,int n)
{
while(left<right)
{
int mid=left+(right-left)/2;
if(a[mid]>a[n-1]) left=mid+1;
else right=mid;
}
return a[left];
}
int main()
{
scanf("%d",&n);for(int i=0;i<n;i++) scanf("%d",&num[i]);
printf("%d",bis(num,0,n-1,n));
}
旋转数组找指定值
严格递增序列
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=100001;int n,num[N];
int bis(int a[],int left,int right,int n,int x)
{
if (x==a[n-1]) return n-1;
if(x<a[n-1])
{
while(left<right)
{
int mid=left+(right-left)/2;
if(a[mid]>a[n-1] || a[mid]<x) left=mid+1;
if(a[mid]>x && a[mid]<a[n-1] ) right=mid-1;
if(a[mid]==x) return mid;
}
return a[left]==x?left:-1;
}
if(x>a[n-1])
{
while(left<right)
{
int mid=left+(right-left)/2;
if(a[mid]>a[n-1] && a[mid]<x) {left=mid+1;}
if(a[mid]>x || a[mid]<a[n-1] ) {right=mid-1;}
if(a[mid]==x) {return mid;}
}
return a[left]==x?left:-1;
}
}
int main()
{
scanf("%d",&n);int x;scanf("%d",&x);for(int i=0;i<n;i++) scanf("%d",&num[i]);
printf("%d",bis(num,0,n-1,n,x));
}
递增序列
也就是可能有相同值
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=100001;int n,num[N];
int bis(int a[],int left,int right,int n,int x)
{
if (x==a[n-1]) //return n-1;
{if (a[0]==a[n-1]) return 0;
else for(int i=n-1;i>0;i--) if(a[i-1]!=x && a[i]==x) return i;
}
if(x<a[n-1])
{
while(left<right)
{
int mid=left+(right-left)/2;
if(a[mid]>a[n-1] || a[mid]<x) left=mid+1;
if(a[mid]>x && a[mid]<a[n-1] ) right=mid-1;
if(a[mid]==x) right = mid;
}
return a[left]==x?left:-1;
}
if(x>a[n-1])
{
while(left<right)
{
int mid=left+(right-left)/2;
if(a[mid]>a[n-1] && a[mid]<x) {left=mid+1;}
if(a[mid]>x || a[mid]<a[n-1] ) {right=mid-1;}
if(a[mid]==x) {right = mid;}
}
return a[left]==x?left:-1;
}
}
int main()
{
scanf("%d",&n);int x;scanf("%d",&x);for(int i=0;i<n;i++) scanf("%d",&num[i]);
printf("%d",bis(num,0,n-1,n,x));
}
旋转序列找中位数：
找到最小值下标+数组长度/2(?)大概，懒得写了
双序列中位数
我用了类似归并排序的方法，代价就是时间复杂度O（n/2）
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=100001;int n,m,num1[N],num2[N];
double s()
{
int a=0,b=0,l=0,l0=(m+n)/2,num3[l0+1];
int c=max(m,n);
while(l<=l0+2 && a<=n-1 &&b<=m-1)
{
if(num1[a]<=num2[b]) {num3[l]=num1[a];a++;l++;}
else{num3[l]=num2[b];b++;l++;}
}
if(l<=l0+2)
{if(a==n) {for(int i=b;i<m&&l<=l0+1;i++){num3[l]=num2[i];l++;}};
if(b==m) {for(int i=a;i<n&&l<=l0+1;i++){num3[l]=num1[i];l++;}};
}
if((m+n)&1) return num3[l0];else return (double(num3[l0])+num3[l0-1])/2;
}
int main()
{//printf("%lf",(double)9/2);
scanf("%d",&n);scanf("%d",&m);for(int i=0;i<n;i++) scanf("%d",&num1[i]); for(int i=0;i<m;i++) scanf("%d",&num2[i]);
printf("%.1f",s());
}
答案仍然是二分，但我没看懂
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 100000;
int n, m, a[MAXN], b[MAXN];
int getMax(int a[], int i, int b[], int j) {
if (i < 0) {
return b[j];
}
if (j < 0) {
return a[i];
}
return max(a[i], b[j]);
}
int getMin(int a[], int i, int b[], int j) {
if (i >= n) {
return b[j];
}
if (j >= m) {
return a[i];
}
return min(a[i], b[j]);
}
double binarySearch(int n, int a[], int m, int b[]) {
int leftPartCount = (n + m + 1) / 2;
int l = 0, r = n;
while (l < r) {
int mid = (l + r + 1) / 2;
int j = leftPartCount - mid;
if (a[mid - 1] > b[j]) {
r = mid - 1;
} else {
l = mid;
}
}
if ((n + m) % 2) {
return (double)getMax(a, l - 1, b, leftPartCount - l - 1);
} else {
return (getMax(a, l - 1, b, leftPartCount - l - 1) + getMin(a, l, b, leftPartCount - l)) / 2.0;
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
for (int i = 0; i < m; i++) {
scanf("%d", &b[i]);
}
if (n < m) {
printf("%.1f", binarySearch(n, a, m, b));
} else {
printf("%.1f", binarySearch(m, b, n, a));
}
return 0;
}