题目地址https://leetcode.com/problems/median-of-two-sorted-arrays/给定两个升序数组A AA和B BB求两个数组所有数的中位数。如果一共偶数个则取最中间的两个数的平均值。设各自的长度n nn和m mm那么如果我们解决了对任意给定的k kk找第k kk小的数这个问题就解决了。所以先考虑如何解决这个更加一般的问题。我们考虑数组A AA和B BB的各自的前k / 2 k/2k/2以下的除法都是整除个数。如果A [ k / 2 − 1 ] B [ k / 2 − 1 ] A[k/2-1]B[k/2-1]A[k/2−1]B[k/2−1]那么我们可以断言A [ 0 ] , . . . , A [ k / 2 − 1 ] A[0],...,A[k/2-1]A[0],...,A[k/2−1]一定都不是答案因为如果存在j ≤ k / 2 − 1 j\le k/2-1j≤k/2−1使得A [ j ] A[j]A[j]是第k kk小的数由于A [ k / 2 − 1 ] B [ k / 2 − 1 ] A[k/2-1]B[k/2-1]A[k/2−1]B[k/2−1]所以比A [ j ] A[j]A[j]还小的数的个数是小于等于j k / 2 − 1 k jk/2-1 kjk/2−1k的这就矛盾了。所以我们就可以将A [ 0 ] , . . . , A [ k / 2 − 1 ] A[0],...,A[k/2-1]A[0],...,A[k/2−1]舍去直接从A [ k / 2 ] A[k/2]A[k/2]开始加上B BB的所有数找第k − k / 2 k-k/2k−k/2小的数。这样就将要找第k kk小的数转变为了要找第k − k / 2 ≤ k / 2 1 k-k/2\le k/21k−k/2≤k/21小的数而且重复这种操作时k kk必然会严格下降到1 11而对于k 1 k1k1答案是显然的。如果A AA的长度是小于k / 2 k/2k/2的那么就可以直接断定B [ 0 ] , . . . , B [ k / 2 − 1 ] B[0],...,B[k/2-1]B[0],...,B[k/2−1]不可能是答案可以直接从B [ k / 2 ] B[k/2]B[k/2]开始和A AA全体中寻找答案剩下的逻辑与上面类似。代码如下classSolution{public:doublefindMedianSortedArrays(vectorintv1,vectorintv2){intnv1.size()v2.size();if(n%2)returnfind(v1,0,v2,0,n/21);elsereturn(find(v1,0,v2,0,n/2)find(v1,0,v2,0,n/21))/2.0;}intfind(vectorintv1,inti,vectorintv2,intj,intk){if(v1.size()-iv2.size()-j)returnfind(v2,j,v1,i,k);if(v1.size()i)returnv2[jk-1];if(k1)returnv1.size()i?v2[j]:min(v1[i],v2[j]);intk1min((int)v1.size()-1,ik/2-1),k2jk-(k1-i1)-1;if(v1[k1]v2[k2])returnfind(v1,k11,v2,j,k-(k1-i1));elseif(v1[k1]v2[k2])returnfind(v1,i,v2,k21,k-(k2-j1));elsereturnv1[k1];}};时间复杂度O ( log ( m n ) ) O(\log (mn))O(log(mn))空间O ( log k ) O(\log k)O(logk)递归栈深度。时间复杂度证明设A AA和B BB的数字个数和为N NN则T ( N , k ) T ( N − k / 2 , k / 2 ) O ( 1 ) T ( N − k / 2 − k / 4 , k / 4 ) O ( 2 ) . . . T ( N − k , 1 ) O ( log k ) O ( log k ) O ( log N ) T(N,k)T(N-k/2,k/2)O(1)\\T(N-k/2-k/4,k/4)O(2)\\...T(N-k,1)O(\log k)O(\log k)O(\log N)T(N,k)T(N−k/2,k/2)O(1)T(N−k/2−k/4,k/4)O(2)...T(N−k,1)O(logk)O(logk)O(logN)极致优化classSolution{public:doublefindMedianSortedArrays(spanintv1,spanintv2){autofind[](thisautofind,spanintv1,inti,spanintv2,intj,intk)-int{intnv1.size(),mv2.size();// Compare v1[i k/2- 1], v2[j k - (k/2 - 1)]// v1[i, i 1, ..., i k/2 - 1]. k/2// v2[j, j 1, ..., j k - k/2 - 1]. k-k/2if(n-im-j)returnfind(v2,j,v1,i,k);if(in)returnv2[jk-1];if(k1)returnmin(v1[i],v2[j]);intk1min(ik/2-1,n-1);intk2jk-(k1-i1)-1;if(v1[k1]v2[k2])returnfind(v1,k11,v2,j,k-(k1-i1));elseif(v1[k1]v2[k2])returnfind(v1,i,v2,k21,k-(k2-j1));elsereturnv1[k1];};intNv1.size()v2.size();if(N%2)returnfind(v1,0,v2,0,N/21);elsereturn(find(v1,0,v2,0,N/2)find(v1,0,v2,0,N/21))/2.0;}};时空复杂度不变。
题目地址https://leetcode.com/problems/median-of-two-sorted-arrays/给定两个升序数组A AA和B BB求两个数组所有数的中位数。如果一共偶数个则取最中间的两个数的平均值。设各自的长度n nn和m mm那么如果我们解决了对任意给定的k kk找第k kk小的数这个问题就解决了。所以先考虑如何解决这个更加一般的问题。我们考虑数组A AA和B BB的各自的前k / 2 k/2k/2以下的除法都是整除个数。如果A [ k / 2 − 1 ] B [ k / 2 − 1 ] A[k/2-1]B[k/2-1]A[k/2−1]B[k/2−1]那么我们可以断言A [ 0 ] , . . . , A [ k / 2 − 1 ] A[0],...,A[k/2-1]A[0],...,A[k/2−1]一定都不是答案因为如果存在j ≤ k / 2 − 1 j\le k/2-1j≤k/2−1使得A [ j ] A[j]A[j]是第k kk小的数由于A [ k / 2 − 1 ] B [ k / 2 − 1 ] A[k/2-1]B[k/2-1]A[k/2−1]B[k/2−1]所以比A [ j ] A[j]A[j]还小的数的个数是小于等于j k / 2 − 1 k jk/2-1 kjk/2−1k的这就矛盾了。所以我们就可以将A [ 0 ] , . . . , A [ k / 2 − 1 ] A[0],...,A[k/2-1]A[0],...,A[k/2−1]舍去直接从A [ k / 2 ] A[k/2]A[k/2]开始加上B BB的所有数找第k − k / 2 k-k/2k−k/2小的数。这样就将要找第k kk小的数转变为了要找第k − k / 2 ≤ k / 2 1 k-k/2\le k/21k−k/2≤k/21小的数而且重复这种操作时k kk必然会严格下降到1 11而对于k 1 k1k1答案是显然的。如果A AA的长度是小于k / 2 k/2k/2的那么就可以直接断定B [ 0 ] , . . . , B [ k / 2 − 1 ] B[0],...,B[k/2-1]B[0],...,B[k/2−1]不可能是答案可以直接从B [ k / 2 ] B[k/2]B[k/2]开始和A AA全体中寻找答案剩下的逻辑与上面类似。代码如下classSolution{public:doublefindMedianSortedArrays(vectorintv1,vectorintv2){intnv1.size()v2.size();if(n%2)returnfind(v1,0,v2,0,n/21);elsereturn(find(v1,0,v2,0,n/2)find(v1,0,v2,0,n/21))/2.0;}intfind(vectorintv1,inti,vectorintv2,intj,intk){if(v1.size()-iv2.size()-j)returnfind(v2,j,v1,i,k);if(v1.size()i)returnv2[jk-1];if(k1)returnv1.size()i?v2[j]:min(v1[i],v2[j]);intk1min((int)v1.size()-1,ik/2-1),k2jk-(k1-i1)-1;if(v1[k1]v2[k2])returnfind(v1,k11,v2,j,k-(k1-i1));elseif(v1[k1]v2[k2])returnfind(v1,i,v2,k21,k-(k2-j1));elsereturnv1[k1];}};时间复杂度O ( log ( m n ) ) O(\log (mn))O(log(mn))空间O ( log k ) O(\log k)O(logk)递归栈深度。时间复杂度证明设A AA和B BB的数字个数和为N NN则T ( N , k ) T ( N − k / 2 , k / 2 ) O ( 1 ) T ( N − k / 2 − k / 4 , k / 4 ) O ( 2 ) . . . T ( N − k , 1 ) O ( log k ) O ( log k ) O ( log N ) T(N,k)T(N-k/2,k/2)O(1)\\T(N-k/2-k/4,k/4)O(2)\\...T(N-k,1)O(\log k)O(\log k)O(\log N)T(N,k)T(N−k/2,k/2)O(1)T(N−k/2−k/4,k/4)O(2)...T(N−k,1)O(logk)O(logk)O(logN)极致优化classSolution{public:doublefindMedianSortedArrays(spanintv1,spanintv2){autofind[](thisautofind,spanintv1,inti,spanintv2,intj,intk)-int{intnv1.size(),mv2.size();// Compare v1[i k/2- 1], v2[j k - (k/2 - 1)]// v1[i, i 1, ..., i k/2 - 1]. k/2// v2[j, j 1, ..., j k - k/2 - 1]. k-k/2if(n-im-j)returnfind(v2,j,v1,i,k);if(in)returnv2[jk-1];if(k1)returnmin(v1[i],v2[j]);intk1min(ik/2-1,n-1);intk2jk-(k1-i1)-1;if(v1[k1]v2[k2])returnfind(v1,k11,v2,j,k-(k1-i1));elseif(v1[k1]v2[k2])returnfind(v1,i,v2,k21,k-(k2-j1));elsereturnv1[k1];};intNv1.size()v2.size();if(N%2)returnfind(v1,0,v2,0,N/21);elsereturn(find(v1,0,v2,0,N/2)find(v1,0,v2,0,N/21))/2.0;}};时空复杂度不变。
