LeetCode 4.寻找两个正序数组的中位数

思路

创建一个新数组，将两个数组合成一个数组，双指针遍历两个数组，将小的数加到新数组当前位置。
这样遍历两个数组时间复杂度就是O(m+n)。

代码

O(m+n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res(2010);
        int first=0,second=0;
        int l1=nums1.size(),l2=nums2.size();
        for(int i=0;i<l1+l2;i++){
            if(first<l1&&second<l2){
                if(nums1[first]<=nums2[second]) res[i]=nums1[first++];
                else res[i]=nums2[second++];
            }else if(first>=l1&&second<l2){
                res[i]=nums2[second++];
            }else if(first<l1&&second>=l2){
                res[i]=nums1[first++];
            }else{
                break;
            }
        }
        if(l1+l2 & 1) return res[(l1+l2)>>1];
        else return (res[((l1+l2)>>1)-1]+res[(l1+l2)>>1])/2.0;
    }
};

O(log(m+n))

参考

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