Mind palace

some thoughts

0%

4. Median of Two Sorted Arrays

Posted on Edited on In Disqus:
Symbols count in article: 3.5k Reading time ≈ 3 mins.

二分法O(log(m+n))
题解
把原题转换成给定两个排好序的数组，找出其中第k小的数（k是1-based）
复杂度计算：少1/4，少1/8，少1/16，直到逼近中位数

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        n = len(nums1) + len(nums2) + 1
        return (self.findKth(nums1, 0, nums2, 0, n // 2) + self.findKth(nums1, 0, nums2, 0, (n + 1) // 2)) / 2 #必须要用self，跟MATLAB一样

    def findKth(self, A: List[int], b1: int, B: List[int], b2: int, k) -> float:
        m, n = len(A) - b1, len(B) - b2
        if m > n: return self.findKth(B, b2, A, b1, k)
        if m == 0: return B[b2 + k - 1]
        if k == 1: return min(A[b1], B[b2])
        i, j = min(k // 2, m), min(k // 2, n)
        if A[b1 + i - 1] < B[b2 + j - 1]: return self.findKth(A, b1 + i, B, b2, k - i)
        return self.findKth(A, b1, B, b2 + j, k - j)
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        def findKth(A, b1, B, b2, k):
            m, n = len(A) - b1, len(B) - b2
            if m > n: return findKth(B, b2, A, b1, k)
            if m == 0: return B[b2 + k - 1]
            if k == 1: return min(A[b1], B[b2])
            i, j = min(k // 2, m), min(k // 2, n)
            if A[b1 + i - 1] < B[b2 + j - 1]: return findKth(A, b1 + i, B, b2, k - i)
            return findKth(A, b1, B, b2 + j, k - j)
        n = len(nums1) + len(nums2) + 1
        return (findKth(nums1, 0, nums2, 0, n // 2) + findKth(nums1, 0, nums2, 0, (n + 1) // 2)) / 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        return (kth(nums1, 0, nums2, 0, (m + n + 1) / 2) + kth(nums1, 0, nums2, 0, (m + n + 2) / 2)) * 0.5;
    }

    int kth(const vector<int> &nums1, int b1, const vector<int> &nums2, int b2, int k) {
        int m = int(nums1.size()) - b1, n = int(nums2.size()) - b2;
        if (m > n) return kth(nums2, b2, nums1, b1, k);
        if (m == 0) return nums2[b2 + k - 1];
        if (k == 1) return min(nums1[b1], nums2[b2]);
        int i = min(m, k / 2), j = min(n, k / 2);
        return nums1[b1 + i - 1] < nums2[b2 + j - 1] ? kth(nums1, b1 + i, nums2, b2, k - i) : kth(nums1, b1, nums2, b2 + j, k - j);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        return (findKth(nums1, nums2, (m + n + 1) / 2) + findKth(nums1, nums2, (m + n + 2) / 2)) * 0.5; // 这里因为是第k大，所以是1-based，(m + n + 1) / 2和(m + n + 2) / 2当m + n是奇数的时候相等，偶数的时候相邻
    }

    double findKth(const vector<int> &A, const vector<int> &B, int k) {
        int m = A.size(), n = B.size();
        if (m > n) return findKth(B, A, k); // 永远保持A比B少
        if (m == 0) return B[k - 1]; // 如果A是空的，直接在B里找
        if (k == 1) return min(A[0], B[0]); // 如果要找第1小的数，直接返回最小的那个
        int i = min(m, k / 2), j = min(n, k / 2); // 每次去掉较小的那k / 2个
        return A[i - 1] < B[j - 1] ? findKth(vector<int>(A.begin() + i, A.end()), B, k - i) : findKth(A, vector<int>(B.begin() + j, B.end()), k - j);
    }
};

O(log(m+n))二分法
把原题转换成找第k小的数，k=(m+n)/2
每次比较两个数组中第k/2大的数，假设nums1[k/2] < nums2[k/2]，则nums1的前k/2元素都不可能是第k大的数，因为至少有剩余的k个数以及nums2[k/2]共k+1个数比这k/2个数大，所以接下来只需要在nums1的剩余数和nums2全部数中找第k-k/2大的数即可。

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
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size() + nums2.size();
        if (n & 1) {
            return findKth(nums1, 0, nums2, 0, (n + 1) / 2);
        } else {
            return (findKth(nums1, 0, nums2, 0, n / 2) + findKth(nums1, 0, nums2, 0, n / 2 + 1)) / 2.0;
        }
    }

    double findKth(const vector<int> &nums1, int s1, const vector<int> &nums2, int s2, int k) {
        if (s1 >= nums1.size()) return nums2[s2 + k - 1];
        if (s2 >= nums2.size()) return nums1[s1 + k - 1];
        if (k == 1) return min(nums1[s1], nums2[s2]);
        int i1 = s1 + k / 2 - 1, i2 = s2 + k / 2 - 1;
        int e1 = i1 >= nums1.size() ? INT_MAX : nums1[i1];
        int e2 = i2 >= nums2.size() ? INT_MAX : nums2[i2];
        if (e1 < e2) {
            return findKth(nums1, s1 + k / 2, nums2, s2, k - k / 2);
        } else {
            return findKth(nums1, s1, nums2, s2 + k / 2, k - k / 2);
        }
    }
};