Leetcode题解学习笔记------第二章数组

代码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];

}
};