题解 | #在两个长度相等的排序数组中找到上中位数#
解题思路
假设两个数轴为2个数组
假设长度为N, 那么 中位数一定在 子区间 a 和 c 之间, 继续二分子区间的位置
中位数无非在 区间 a 和 c之间,如何缩小范围呢?
例如:
arr1[1,2,3,4,5]
arr2[3,4,5,6,7]
我们可以看到arr2[2]<arr2[2],则此时从arr1[0]到arr1[2]这段区间的数是必然比中位数小的。此时 l 则指向位置2即arr[2]=3这个位置。
我们可以看到arr2[2]<arr2[2],则此时从arr1[0]到arr1[2]这段区间的数是必然比中位数小的。此时 l 则指向位置2即arr[2]=3这个位置。
每次回丢弃掉 数组的一半,推导时间复杂度为
即
时间复杂度为 o(logN)
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * find median in two sorted array * @param arr1 int整型vector the array1 * @param arr2 int整型vector the array2 * @return int整型 */ int findMedianinTwoSortedAray(vector<int> &arr1, vector<int> &arr2) { int n = arr1.size(), m = arr2.size(); if (n != m) return -1; if(n==0) return 0; if(n==1) return min(arr1[0],arr2[0]); int l = 0,r =n-1,x=0,y = n-1; while(l<r) { int even = (r-l) % 2 !=0;//偶数为1,奇数为0 ,例如{0,1} => 1-0=1 % 2 != 0 int m = l+(r-l)/2; int m2 = x+(y-x)/2; if(arr1[m] == arr2[m2]) return arr1[m]; else if(arr1[m] < arr2[m2]) { l = m+even; //长度为偶数的子区间中值后一位才是右半部分的起点 y = m2; }else { r = m; x = m2 + even; } } return min(arr1[l],arr2[x]); } int _findMedianinTwoSortedAray(vector<int> &arr1, vector<int> &arr2) { // write code here int n = arr1.size(), m = arr2.size(); int total = n + m; int K = (total / 2); // if(total %2==0) K++; // println("K",K); //第K个最大数 priority_queue<int> q; int l = 0, r = 0; while (q.size() < K) { if (arr1[l] <= arr2[r]) { q.push(arr1[l++]); } else { q.push(arr2[r++]); } } // if(total % 2==0) { // int l = q.top(),q.pop(); // return (l+q.top()) /2; // } return q.top(); } }; #ifdef debug int main(void) { Solution k; vector<int> a{1,9,19}; vector<int> b{2,5,10}; // 1 2 3 (3 4) 4 5 6 println(k.findMedianinTwoSortedAray(a, b)); } #endif
算法常用解题技巧 文章被收录于专栏
算法常用解题技巧