代码2和代码3完全看不懂。。。该题就是查找重复元素以及设置重复次数。

 

在一个旋转过的有序数组中查找指定元素：（实际上就是一个二分查找问题，确定边界问题）

 

首先涉及到有序数组被旋转过了，你不用管它怎么旋转，怎样旋转。反正就是前面一段大，后面一段小。该题就是二分查找的边界确定问题。二分查找的时间复杂度怎么回是(log n)呢。

 

class Solution{

public:

int search(vector<int>& nums,int target){

int first=0;

int last=nums.size()-1;

int mid=(first+last)/2;

if(target=nums[mid])

return mid;

else{//start to search

if(nums[first]<nums[mid])//chose the bigger part

{

if(nums[first]<=target&&nums[mid]>target)

last=mid;

else

first=mid+1;

}

else{//chose the smaller part

if(nums[mid]<target&&target<=nums[last])

first=mid+1;

else

last=mid;

}

}

return -1;

}

 

};编译没通过，虽然我不知道为什么

 

变形:如果允许出现重复元素。实质就是nums[first]和nums[mid]之间的关系从上题的两种变为了三种。

代码略

寻找两个有序数组的中间元素：等价于寻找第K大的元素。

 

 

class Solution{

public:

double FindKth(const vector<int>& A,const vector<int>& B){

int total=A.size()+B.size();

//实质上就是寻找第K个元素

if(total%2==1)

return FindKth(A.begin(),m,B.begin(),n,total/2+1);

else

return (FindKth(A.begin(),m,B.begin(),n,total/2)+FindKth(A.begin(),m,B.begin(),n,total/2+1))/2;

 

}

private:

int FindKth(A,m,B,n,k){

//永远假定m小于等于n

if(m>n)

return FindKth(A,n,B,m,k);

//start to devide K into two parts

int ia=min(k/2,m); int ib=k-ia;

if(*(A+ia-1)<*(B=ib-1))

return FindKth(A+ia,m-ia,B,m,k-ia);

else if(*(A+ia-1)>*(B=ib-1))

return FindKth(A,m,B+ib,m-ib,k-ib);

else

return A[ia-1];

 

}

};