4. 寻找两个正序数组的中位数

题目链接

解题思路

• 用双指针，或者辅助数组的方法这里就不过多解释了，现在说最优解。
• 我们可以利用两个数组「有序」的特点，找到其中位数。
• 直接举例子，假设其中一个数组nums1是[1, 3, 5, 7, 9]，另一个数组nums2是[2, 4, 6, 8]，中位数我们先人工算出来，是5，也就是整体的第5小的数，也就是说，我们目的就是找整体第5小的数。
  • 先在nums1中取中位数， 5，然后在nums2中，找到小于等于5，最右侧的位置，就是4，然后我们可以计算，nums2中，2, 4是两个数，nums1中1,3,5是三个数，然后，这5个数，正好等于我们要找到第5小的数，所以直接返回5了。
• 可能还有些抽象，其实思路很简单，就是第一个数组，在[L1, R1]上，第二个数组[L2, R2]上，求第k小。我首先得到mid = (R1+L1)/2，然后在nums2中找到小于等于nums1[mid]最右侧的位置，假设是x，那么我们就可以知道nums1中，一共有mid - L1 + 1个数，nums2中，一共有x - L2 + 1个数，一共y个数，
  • 如果k == y，那么我们可以直接返回nums1[mid]
  • 如果k < y，那么我们可以在[L1, mid]以及[L2, x]中，继续找第k小的数
  • 如果k > y，那么我们可以在[mid + 1, R1] 以及[x + 1, R2]中，继续找第y - k小的数
• 还有点懵？看代码，边看边理解。
• 感性地感觉，每次能淘汰一半长度的数。而在「nums2中找到小于等于nums1[mid]最右侧的位置」，可以使用二分法找，所以时间复杂度是O(log(n + m))

代码

class Solution {
public:
    // 在nums1[L1, R1]和nums2[L2, R2]上，找到第k小的数
    int process(vector<int> &nums1, vector<int> &nums2, int L1, int R1, int L2, int R2, int k) {
        if (L1 > R1) {   // nums1没有数了 也就是说  直接找到nums2第k小的数即可
            return nums2[L2 + k - 1];
        }
        int mid1 = (R1 + L1) / 2;
        int i = L2;
        int j = R2;
        int index = -1;
        // 在nums2[L2, R2]中，找到小于等于nums1[mid1]的最右的位置
        while(i <= j) {
            int mid = (i + j) / 2;
            if (nums1[mid1] >= nums2[mid]) {
                index = mid;
                i = mid + 1;
            }else {
                j = mid - 1;
            }
        }
        if (index == -1) {    // 没有找到，也就是说nums2[L2, R2]所有的数，都大于nums1[mid1]
            if (mid1 - L1 + 1 > k) {
                return nums1[L1 + k - 1];
            } else if(mid1 - L1 + 1 == k) {
                return nums1[mid1];
            } else {
                return process(nums1, nums2, mid1 + 1, R1, L2, R2, k - mid1 + L1 - 1);
            }
        } else {   // 找到了
            if (mid1 - L1 + 1 + index - L2 + 1 > k) {
                // 注意 变成了nums1[L1, mid1-1] 和nums2[L2, index]
                // 因为nums1[mid1]是 nums1[L1, mid1] 和nums2[L2, index]最大的数  mid1可以被淘汰了
                // 并且，如果不是mid1 - 1，这里可能进入死递归
                return process(nums1, nums2, L1, mid1 - 1, L2, index, k);
            } else if(mid1 - L1 + 1 + index - L2 + 1 == k) {
                return nums1[mid1];
            } else {
                return process(nums1, nums2, mid1 + 1, R1, index + 1, R2, k - mid1 + L1 - 2 - index + L2);
            }
        }
    }


    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int m = nums2.size();
        if ((n + m) % 2 == 0) {   // 长度和是偶数  要找两个
            double ans1 = process(nums1, nums2, 0, n - 1, 0, m - 1, (n + m) / 2);
            double ans2 = process(nums1, nums2, 0, n - 1, 0, m - 1, (n + m) / 2 + 1);
            return (ans1 + ans2) / 2;
        } else {    // 长度和是奇数   找一个
            return process(nums1, nums2, 0, n - 1, 0, m - 1, (n + m) / 2 + 1);
        }
    }
};