LeetCode--Median of Two Sorted Arrays

发表于 | 分类于 |

题目描述：

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.

样例：

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

The median is 2.0
1
2
3
4
nums1 = [1, 2]
nums2 = [3, 4]

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

题意：

给出两个排好序的数组，找出这两个数组中的中位数。

思路：

其实蚊子的思路，就是直接暴力，就用一个 vector 存储重新生成的排好序的数组，然后直接就找到了中位数了，这道题之所以会被标为 hard 估计是因为题目中的 O(log(m +n)) 的时间复杂度叭，不过蚊子肯定会找到这么少的时间复杂度的，那现在蚊子就暂时将蠢蠢的做法贴出来叭。

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) {
        vector<int> ve;
        int len1 = 0, len2 = 0;
        while(len1 < nums1.size() && len2 < nums2.size()){
            if(nums1[len1] < nums2[len2]){
                ve.push_back(nums1[len1]);
                len1++;
            }
            else if(nums1[len1] > nums2[len2]){
                ve.push_back(nums2[len2]);
                len2++;
            }else{
                ve.push_back(nums1[len1]);
                len1++;
                ve.push_back(nums2[len2]);
                len2++;
            }
        }
        while(len1 < nums1.size()){
            ve.push_back(nums1[len1]);
            len1++;
        }
        while(len2 < nums2.size()){
            ve.push_back(nums2[len2]);
            len2++;
        }
        int n = len1 + len2;
        double ans = (ve[(n - 1) / 2] + ve[n / 2]) / 2.0;
        return ans;
    }
};

Rumtime：44ms Memory：22.2MB

好吧，蚊子还是别人的代码贴上来吧，嘤嘤嘤

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size(), left = (m + n + 1) / 2, right = (m + n + 2) / 2;
        return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0;
    }
    int findKth(vector<int>& nums1, int i, vector<int>& nums2, int j, int k) {
        if (i >= nums1.size()) return nums2[j + k - 1];
        if (j >= nums2.size()) return nums1[i + k - 1];
        if (k == 1) return min(nums1[i], nums2[j]);
        int midVal1 = (i + k / 2 - 1 < nums1.size()) ? nums1[i + k / 2 - 1] : INT_MAX;
        int midVal2 = (j + k / 2 - 1 < nums2.size()) ? nums2[j + k / 2 - 1] : INT_MAX;
        if (midVal1 < midVal2) {
            return findKth(nums1, i + k / 2, nums2, j, k - k / 2);
        } else {
            return findKth(nums1, i, nums2, j + k / 2, k - k / 2);
        }
    }
};