Leetcode-Median of Two Sorted Arrays
- 前言
- 题目分析1
- 算法的正确性
- 代码
- 效率
- 题目分析2
- 算法的正确性
- 代码
- 效率
- 推广
- 结语
前言
Leetcode刷到150道了，各种题型都已经练习了一遍，没有必要再去刷数量了！分类总结解题方法，完善知识体系已经是刻不容缓了。尤其是在看了《暗时间》之后，深有感触。总结、反思自己的思维过程也许是最重要的。对每道题进行深加工，抽象出一般的概念，得到一般的解题策略。这个过程才是最重要的，是沉淀思想的绝好途径。
先简单摘一些常用的解题方法，以后每碰到难题的时候，都要想一下用这些方法是否可以解决：
时刻不忘未知量
时刻要想到自己的问题是什么，要求什么。用特例启发思考
构造一个合适的实例，可能会发现一般的规律。反过来推导
设立未知数，从结论出发，向已知条件靠扰。试错
- 调整题目的条件
去掉一个条件，观察区别，再放上那个条件，感觉到题目的内在结构上的某种约束，进而得到答案。 - 求解一个类似的题目
为了优化脑中的知识结构，我们在记忆掌握和分析问题的时候都应该尽量抽象地去看待，这样才能建立知识的本质联系。 - 列出所有可能与题目有关的定理或性质
比如这道题目，可以列出这样的性质：中位数是数组中最中间的数。如果元素总数为奇数，它左边所有元素的个数和右边所有元素的个数相等；如果为偶数，则将所有元素平分成两左右两部分，两部分元素个数相等， 中位数为最中间两者的均值。 - 考察反面，考察其他所有情况
- 将问题泛化
这道题应该要进行泛化，比如如果要求两个排序元素里的第K大元素怎么求？如果是n个排序数组呢？
题目分析1
Leetcode-CPP_p14可以从结论来推导方法：题目要求用log(m+n)的复杂度，而中位数的序号为i=m+n2，要想达到要求的复杂度，则每次查找都应该使i减半，即要用到二分搜索。那怎样才能用到二分搜索呢？这一步还不是那么明显，答案是将原问题泛化，寻找两个排序数组的第k小的数，然后每步排除k/2个数，则最后可以达到复杂度要求。
假设A,B两个数组的元素个数都大于k/2，那么将A,B的第k个元素，也就是A[k2−1]和B[k2−1]作比较的话，
⎡⎣⎢⎢⎢A[0]B[0]A[1]⋯B[1]⋯A[k2−1]B[k2−1]A[k2]⋯B[k2]⋯⎤⎦⎥⎥⎥
可以得到：
⎧⎩⎨⎪⎪⎪⎪A[k2−1]<B[k2−1],A[k2−1]>B[k2−1],A[k2−1]==B[k2−1],(1)(2)(3)
对于情形(1)，A[0]⋯A[k2−1]一定是排在B[k2−1]之前，因此A[0]⋯A[k2−1]绝对不会是第k小的数，可以在下一轮寻找中去掉，因此下一轮比较将变成：
⎡⎣⎢⎢⎢A[k2]B[0]⋯B[1]⋯A[k2+k4−1]B[k4−1]⋯B[k4]⋯⎤⎦⎥⎥⎥
这里我们不能排除B中的元素，是因为我们仅仅知道A[k2−1]与B[k2−1]的大小关系，而不知道A[k2−1]与B[0]的关系，B[0]可以很大，以至于大于A[k2−1]，而这个时候，其实我们是得不出进一步的结论的，因为我们还是不知道B[0]和A[k2−1]后面元素的关系。当然，另一方面，B[0]可以比较小，以至于当它增加到B[k2−1]时只比A[k2−1]大了一点点，且小于A[k2]，那么B[k2−1]就是我们要找的第k小的数，只是找到它还需要再递归几次。而这并不难分析。
因为我们是要寻找第k小的数，永远不要忘了我们的目的是什么——走得太远，不要忘了当初是为什么出发！而我们已经排除了k2个数，因此下一步是寻找第k2（这里的第k2是指包括当前元素的元素个数）小的数，因而又可以排除一半的数，即k4。
情形(2)的分析类似；
而情形(3)就更简单了，直接可以得到要找的数就是A[k2−1]。因为一定可以得到下面的排列：
A[0]⋯A[k2−2]⋯B[0]⋯B[k2−2] A[k2−1] B[k2−1]
虽然我们不知道A⋃B中的前k−2个数的具体顺序，但是最后两个数一定是A[k2−1],B[k2−1]，而最后一个数正是我们要找的第k小的数。
算法的正确性
如何证明算法的正确性呢？
每次递归都会排除一半的元素或者排除掉整个数组，即当k2>m，最后一定会得到正确的结果。
代码
int getKth(int a[], int m, int b[], int n, int k) {if (m > n)return getKth(b, n, a, m, k);if (0 == m)return b[k-1];if (1 == k)return min(a[0], b[0]);int i = min((k+1)/2, m);/*if (a[i-1] < b[i-1])return getKth(a+i, m-i, b, n, k-i);else if (a[i-1] > b[i-1])return getKth(a, m, b+i, n-i, k-i);*/int j = k-i;if (a[i-1] < b[j-1])return getKth(a+i, m-i, b, n, k-i);else if (a[i-1] > b[j-1])return getKth(a, m, b+i, n-i, k-j);elsereturn a[i-1]; }double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {int total = nums1Size+nums2Size;if (total & 1) //oddreturn getKth(nums1, nums1Size, nums2, nums2Size, total/2+1);else //evenreturn (getKth(nums1, nums1Size, nums2, nums2Size, total/2+1) + getKth(nums1, nums1Size, nums2, nums2Size, total/2))/2.0; }代码中注释的地方是有问题的，如果只是比较A[i−1]和B[i−1]，那么无论i是等于k2还是等于k+12，最后都是不能直接用后面三种情况来处理的。所以我们还需要一个变量j=k−i来保证目前我们比较的元素个数为k。还是那句话，不要忘了最初的目的是什么。
所以这里的关键在于选出k个数，比较每个一维数组的最后一个元素的大小。对于kn大于一维数组的长度m的情形，就会越界，这时只能取m个元素了，那另外一个数组就必须取k−m个元素了，对于n==2时，显然k−m对于第2个数组是不越界的。但对n>2的情形，则情况会复杂很多。
下面是用vector加上迭代器的代码：
int getKthOfVectors(vector<int>& nums1, vector<int>::iterator it1, vector<int>& nums2, vector<int>::iterator it2, int k) {int sz1 = nums1.end()-it1;int sz2 = nums2.end()-it2;if (sz1 > sz2)return getKthOfVectors(nums2, it2, nums1, it1, k);if (0 == sz1)return *(it2+k-1);if (1 == k)return min(*it1, *it2);int i = min((k+1)/2, sz1);int j = k-i;if (*(it1+i-1) < *(it2+j-1)){it1 += i;return getKthOfVectors(nums1, it1, nums2, it2, k-i);} else if (*(it1+i-1) > *(it2+j-1)){it2 += j;return getKthOfVectors(nums1, it1, nums2, it2, k-j);} elsereturn *(it1+i-1); }double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int total = nums1.size()+nums2.size(); if (total & 1) //oddreturn getKthOfVectors(nums1, nums1.begin(), nums2, nums2.begin(), (total+1)/2);else //evenreturn (getKthOfVectors(nums1, nums1.begin(), nums2, nums2.begin(), total/2+1)+getKthOfVectors(nums1, nums1.begin(), nums2, nums2.begin(), total/2))/2.0; }效率
假定n是要找的第n小的数。则：
T(n)=T(n/2)+O(1)，由主定理⇒T(n)=logn。
题目分析2
根据discuss里分享的解答，还可以利用中位数的这一性质：中位数两边的元素个数相等（或相差1）。列出这一性质并不难，难就难在怎么根据这一性质继续往下走。
⎡⎣⎢⎢A[0]B[0]left partA[1]⋯B[1]⋯A[i−1]B[j−1]right partA[i]⋯B[j]⋯A[m−1]B[n−1]⎤⎦⎥⎥
当左右两部分的元素个数相等或者相差1时，而且A[i]>B[j−1],B[j]>A[j−1]，那么中位数就不难找出来了。因此我们只要找出i
由此，可列方程i+j=m−i+n−j或者i+j=m−i+n−j+1
{i+j=m−i+n−j,i+j=m−i+n−j+1,(m+n为偶数)(m+n为奇数)
⇒
{j=m+n2−i,j=m+n+12−i,(m+n为偶数)(m+n为奇数)
⇒
j=m+n+12−i(将m+n为奇数和偶数统一起来)
因此我们只要在0~m中寻找i，就可以得到解答，而且由于是寻找中位数，它一定是存大的，就是说我们用binary search来寻找i，是一定能找到的。值得注意的是，这里的i∈[0,m]，当i==0时，A全部在left part，当i==m时，A全部在rigth part部分。
算法的正确性
每次查找，要么找到i，要么会缩小查找范围，而i一定是存在的，所以最后一定能找到i。
代码
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int sz1 = nums1.size();int sz2 = nums2.size();if (sz1 > sz2)return findMedianSortedArrays(nums2, nums1);int imin = 0;int imax = sz1;int i, j;while (imin <= imax){i = (imin+imax)/2;j = (sz1+sz2+1)/2 - i;if (i > 0 && j < sz2 && nums2[j] < nums1[i-1])imax = i-1;else if (j > 0 && i < sz1 && nums1[i] < nums2[j-1])imin = i+1;else break;}int num1;if (0 == i)num1 = nums2[j-1];else if (0 == j)num1 = nums1[i-1];elsenum1 = max(nums1[i-1], nums2[j-1]);if ((sz1+sz2) & 1) //oddreturn num1;int num2 = min(nums1[i], nums2[j]);return (num1+num2)/2.0; }注意：代码最后返回时用到除法，除数要用2.0，否则返回的是int类型转换到double，结果错误。
效率
二分查找的效率当然是log2min(m,n)。
推广
如果是在n个已排序的数组，寻找第k小的数，该怎么求呢？
根据思路1，我们可以比较每个数组的第kn个数，如果全部相等，则找到第k小的数；否则，可以排除(n−1)kn个数，只有最大的那个元素所在的数组不能排除掉。
上面所说的是理想情况下，实际写代码的时候要考虑的东西稍复杂一些，当数组的元素个数小于kn时，明显就会越界。再有首先得保证，所有数组的元素总数一定大于k的。
因此，可以推广为找出二维vector中的第k小的数。
接口为：
double findMedianSortedArrays(vector<vector<int>> &nums, int k)效率又该怎么计算呢？
这里n和k均有可能是变量，为了更好的与主定理对应，我们用
n表示输入的规模，即
(1)如果是在n个已排序的数组，寻找第b小的数
复杂度与n其实没有关系，只与b有关，因此T(n)=O(1)。
(2)如果是在b个已排序的数组，寻找第n小的数
每次递归后n都会变成原来的1b⇒T(n)=T(n/b)+O(1)，由主定理⇒T(n)=logn。
最坏情况下，每次只能排除一个数，那么时间复杂度就会降为O(n)
结语
如果n维数组的每维的长度相等，还比较好办。如果每维的长度不等，对于最好情况下的每次递归后规模变成原来的1n就会退化成每次递归后规模只减了1。所以，以上的思路只对2个已经排序的一维数组有比较好的效果。
不管怎么说，第一篇博客，加油！！！
总结
以上是生活随笔为你收集整理的Leetcode-Median of Two Sorted Arrays的全部内容，希望文章能够帮你解决所遇到的问题。
- 上一篇： 一个卑微的程序员友链
- 下一篇： [STL]priority_queue