1. Median of Two sorted Array
首先看总元素个数N是奇数还是偶数，奇数的话中位数 index(1 开头)k就是N/2+1 偶数的话就是N/2. N/2+1的平均数。然后就是求AB 的第K个数。要求A的长度小于B。 如果A的长度是0 那么返回B[k-1]. 否则的话，取pa=min(k/2, m), m是A的长度，pb=k-pa。 这里主要是让k每次一半递减，也就是说 要去掉k/2的元素（从A，B里）找第k/2大的元素就是答案。那么正确的去掉这k/2的元素就是关键 （并不是说去掉最小的k/2个元素，而是说这k/2个元素肯定是前K个里面的）因此如果A[pa-1]<=B[pb-1] 那么A的前Pa个元素就要被去掉 (Pa+Pb==K). 详见代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | double fms(int A[], int m, int B[], int n,int k){ if(m>n) return fms(B,n,A,m,k); if(m==0) return B[k-1]; if(k==1) return min(A[0],B[0]); int pa=min(k/2,m); int pb=k-pa; if(A[pa-1]<=B[pb-1]) return fms(A+pa,m-pa,B,n,k-pa); else return fms(A,m,B+pb,n-pb,k-pb); } double findMedianSortedArrays(int A[], int m, int B[], int n) { // Start typing your C/C++ solution below // DO NOT write int main() function int total =m+n; if(total%2==1) return fms(A,m,B,n,total/2+1); else return (fms(A,m,B,n,total/2)+fms(A,m,B,n,total/2+1))/2; } |
2. Search in rotated array
思路并不难，如果A[start]<A[mid] 证明 [start,mid] 这段是排好序的。若A[start]<=target&&taget<A[mid] end=mid-1;否则start=mid+1. 如果A[mid]<A[end] 证明[mid,end]这段是排好序的。
这道题目重点两个: while 条件 start<=end. 判断时A[start]<=target 而不是A[start]<target.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | int search(int A[], int n, int target) { // Start typing your C/C++ solution below // DO NOT write int main() function int l=0; int r=n-1; while(l<=r){ int mid=(l+r)/2; if(A[mid]==target) return mid; if(A[l]<=A[mid]){ if(A[l]<=target&&target<A[mid]) r=mid-1; else l=mid+1; } else{ if(A[r]>=target&&target>A[mid]) l=mid+1; else r=mid-1; } } return -1; } }; |
duplicates are allowed. 主要是处理A[l]==A[mid]的情况 l++ skip.
3. Search for a Range
其实是求第一个target 的 index(low）和最后一个target的index(upp)。方法有多种，这里介绍的方法是这样：初始化start=0;end=n; 最后下届就是start, 上届就是end-1. 在这个过程中，有这么几个变量公式需要保证： 求下届时, A[low]=第一个target, A[upp]>=target. 所以当A[mid]<=target的时候 upp=mid. 因为如果是upp=mid-1的话有可能漏过的这个是唯一的target. 求上届时，A[upp]是第一个比target大的元素。因此当A[mid]>target的时候 upp=mid.这样能保证upp>target. 此时low也只是参照，只要保证low小于upp.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | bool search(int A[], int n, int target) { // Start typing your C/C++ solution below // DO NOT write int main() function int l = 0, r = n - 1; while (l <= r) { int m = (l+r)/2; if (A[m] == target) return true; //return m in Search in Rotated Array I if (A[l] < A[m]) { //left half is sorted if (A[l] <= target && target < A[m]) r = m - 1; else l = m + 1; } else if (A[l] > A[m]) { //right half is sorted if (A[m] < target && target <= A[r]) l = m + 1; else r = m - 1; } else l++; } return false; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | vector<int> res(2,-1); int l=0; int r=n-1; while(l<=r){ int m=l+(r-l)/2; if(A[m]==target){ if(m==0||A[m-1]<A[m]){ res[0]=m; l=m; r=n-1; } if(m==n-1||A[m]<A[m+1]){ res[1]=m; r=m; l=0; } if(res[0]>=0&&res[1]>=0) return res; if(res[0]==-1) r=m-1; else l=m+1; } else if(A[m]<target) l=m+1; else r=m-1; } return res; |
如果数组元素个数是n， 那么插入位置是0...n. 初始化 start=0, end=n-1. 最后的终止状态是start=end=mid. 因此 while loop start<=end. 然后if A[mid]< target return mid+1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | int searchInsert(int A[], int n, int target) { // Start typing your C/C++ solution below // DO NOT write int main() function int start = 0; int end = n-1; int mid = 0; while(start <= end) { mid = (start + end) / 2; if(A[mid] == target) return mid; else if(A[mid] < target) start = mid +1; else end = mid-1; } if(A[mid] < target) return mid+1; else return mid; } |
如果按行扫描，这其实是一个一维排好序的数组。关键是把二维index转换为一维index A[i]=A[i/col][i%col]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | bool searchMatrix(vector<vector<int> > &matrix, int target) { // Start typing your C/C++ solution below // DO NOT write int main() function int rows=matrix.size(); int cols=matrix[0].size(); int start=0; int end=rows*cols-1; while(start<=end){ int mid=(start+end)/2; if(matrix[mid/cols][mid%cols]==target) return true; else if(matrix[mid/cols][mid%cols]<target) start=mid+1; else end=mid-1; } return false; } |
没有评论:
发表评论