LeetCode 4 Median of Two Sorted Arrays

Tag: 二分搜索 LeetCode Posted on 2022-03-05 09:47:28 Edited on 2022-03-05 10:59:39 Views: 151

概述

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,

为了找到中位数,

  1. 我们需要将数组分割为两个等数量的部分,因此 i + j = (m + n + 1) / 2,则 int j = halfLenght - i;,m <= n 使得 j 不至于为负数,
  2. 同时,前一个部分的最大值(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;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/