leetcode 4 -- Median of Two Sorted Arrays

Posted on | In

题目重述

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)).
You may assume nums1 and nums2 cannot be both empty.

两个有序的数组nums1和nums2，其大小分别为m和n。
请找到两个数组排序后的中位数，总运行时间复杂度应为O（log（m + n））。
您可以假设nums1和nums2不能都为空。

Example1：

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

The median is 2.0

Example2：

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

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

解题思路

这道题目比较简单，下意识的想法就是使用归并的方法将两个有序的数组进行排序即可很方便地找到中位数，即新建一个结果数组，依次比较两个数组中的最小值，将更小的值放入结果数组中，一共需要比较m+n-1次。

而由于我们需要得到的结果局哟特殊性——是序列中间的数字，也就是说，在上述归并过程中，我们并不需要得到完整的结果队列，只需要找到结果队列的前(m+n)/2个数据就能够找到中位数，同时，我们也自然地想到，我们并没有必要创建一个数组来存储小于中位数，只需要在前(m+n)/2次判断中找到最大值即可。这时，问题已经被简化为进行(m+n)/2次（实际需要+1）比较得到结果的过程了。

而此时又出现新的问题：当m+n为奇数时，中位数为合并后的序列的第(m+n)/2+1个值，而当m+n为偶数时，则是第(m+n)/2和第(m+n)/2+1个值的平均数。此时我们可以发现，第(m+n)/2和(m+n)/2+1都可能是我们关注的值，而对于这两个数据，我们只需要进行(m+n)/2+1次比较，并记录每次比较结果next及其前一次比较结果before即可，最后根据m+n的奇偶性决定最终结果应该是next还是(next+before)/2。

当然我们还要注意，最终的结果应该是double类型。

代码编写

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
26
27
28
29
30
31
32
33
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int totallength = nums1.size() + nums2.size();
        int i = 0, j = 0, curr = 0, before = 0, next = 0;
        while(curr < totallength/2+1){
            before = next;
            if(i == nums1.size()){
                next = nums2[j];
                j++;
            }
            else if (j == nums2.size()){
                next = nums1[i];
                i++;
            }
            else if(nums1[i] < nums2[j] ){
                next = nums1[i];
                i++;
            }
            else{
                next = nums2[j];
                j++;
            }
            curr++;
        }
        if(totallength % 2 == 1){
            return next;
        }
        else{
            return double(before+next)/2;
        }
    }
};

代码见github

运行结果

accept

runtime

memory

感觉自己的方法很常规，不是很快，如果有大佬做得更快希望不吝赐教~

0%