欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Median of Two Sorted Arrays Leetcode #4 题解[C++]

程序员文章站 2022-06-03 10:37:03
...

题目来源


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

题意解析


There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:
nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

给出两个排好了序的数组, 求出这两个数组的中位数, 要求时间复杂度为O(log(m+n)).

解题思路


这道题想了很久都没有做出来, 想到的最快方法也是O((m-n)log(m+n)), 后来参考了讨论区的一份帖子才最终AC,

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

这里大概讲一下帖子所提供的思路.

中位数本身的含义就是它之前的数和它之后的数一样多. 因此, 想通了这一点, 我们就能把问题简化的多, 我们像下面这样把所有数割成左右两部分, 使得左边的数等于右边的. 并且满足max(left_part) <= min(right_part).

      left_part          |        right_part
A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]
B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]

这样一来, 利用A[i-1], A[i], B[j-1], B[j]这几个数我们便能求出所需的中位数.
不失一般性, 假设len(A)=m < len(B)=n, 令 i 取[0,m], 令 j 取(m + n + 1)/2 - i, 这样就能保证左右两边的数字总数相同.

接下来只需要设法满足max(left_part) <= min(right_part)即可. 既然已经知道了 i 的取值范围, 我们通过二分查找来寻找满足这一条件的 i 的值即可.

代码实现


class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        if (n < m) return findMedianSortedArrays(nums2, nums1);
        int i, j,max_left,min_right;
        int imin = 0;
        int imax = m;
        int half_len = (m + n + 1) / 2;
        while (imin <= imax) {
            i = (imin + imax) / 2;
            j = half_len - i;
            //i should be bigger
            if (i<m&&nums2[j - 1]>nums1[i]) imin = i + 1; 
            //i should be smaller
            else if (i > 0 && nums1[i - 1] > nums2[j]) imax = i - 1; 
            //We have found i that satisfied our requirement.
            else {
                //Don't forget to consider edge conditions.
                if (i == 0) max_left = nums2[j - 1];
                else if (j == 0) max_left = nums1[i - 1];
                else max_left = max(nums1[i - 1], nums2[j - 1]);

                //If total nums is odd then only need to return max_left.
                if ((n + m) & 1) return max_left;

                if (i == m) min_right = nums2[j];
                else if (j == n) min_right = nums1[i];
                else min_right = min(nums1[i], nums2[j]);
                return double(min_right + max_left) / 2.0;
            }

        }
    }
};

Median of Two Sorted Arrays Leetcode #4 题解[C++]

相关标签: Algorithm