LeetCode 4 Median of Two Sorted Arrays

    
        标签：
        
            二分搜索
        
            LeetCode
        
    发布于：2022-03-05 09:47:28
    编辑于：2022-03-05 10:59:39
    浏览量：758

概述

https://leetcode.com/problems/median-of-two-sorted-arrays/

这是一道困扰了我好久的 Hard 题。

题目要求 O(log (m+n))

暴力法

有序地合并两个数组，之后直接给出中位数。

时间复杂度 O(m+n)。

二分搜索

https://leetcode.com/problems/median-of-two-sorted-arrays/discuss/2481/Share-my-O(log(min(mn)))-solution-with-explanation

两个数组的总长度为 m + n，题目要求 O(log (m+n))，所以想到二分搜索很自然。

二分搜索，搜索什么呢？

设 A 的长度为 m，B 的长度为 n，不妨假设 m <= n，设 A 中分割索引为 i，B 中分割索引为 j，

为了找到中位数，

我们需要将数组分割为两个等数量的部分，因此 i + j = (m + n + 1) / 2，则 int j = halfLenght - i;，m <= n 使得 j 不至于为负数，
同时，前一个部分的最大值（A[i-1] 和 B[j-1]）小于等于后一个部分的最小值（A[i]和 B[j]），因为 A[i-1] 本来就小于 A[i]，以及 B[j-1] 本来就小于 B[j]，所以只需要满足：A[i-1] <= B[j] && B[j-1] <= A[i]

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int> A = nums1, B = nums2;
        if (nums1.size() > nums2.size()) {
            A = nums2;
            B = nums1;
        }
        int m = A.size();
        int n = B.size();
        int halfLength = (m + n + 1) / 2;
        int imin = 0, imax = m;
        while (imin <= imax) { // this means i can be imin & imax
            int i = (imin + imax) / 2;
            int j =  halfLength - i;
            if (i < m && B[j-1] > A[i]) {  // i too small
                imin = i + 1;
            } else if (i > 0 && A[i-1] > B[j]) {  // i too large
                imax = i - 1;
            } else {
                // i found
                int leftMax = 0;
                if (i == 0) {
                    leftMax = B[j-1];
                } else if (j == 0){
                    leftMax = A[i-1];
                } else {
                    leftMax = max(A[i-1], B[j-1]);
                }
                if ((m + n) % 2 == 1) return leftMax;
                int rightMin = 0;
                if (i == m) {
                    rightMin = B[j];
                } else if (j == n) {
                    rightMin = A[i];
                } else {
                    rightMin = min(A[i], B[j]);
                }
                return (leftMax + rightMin) / 2.0;
            }
        }
        return -1;
    }
};

Links: leetcode-4-median-of-two-sorted-arrays