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

发表于 分类于 ， 阅读次数： 本文字数： 97 阅读时长 ≈ 1 分钟

思路: 先归并排序, 再寻找中间位置

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
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int i=0,j=0;
        int len1=nums1.size(),len2=nums2.size(),len=len1+len2;
        int t, lastt;
        while(i+j<=len/2){
            lastt=t;
            if(i<len1 && j< len2){
                int n1=nums1[i];
                int n2=nums2[j];
                if(n1<n2){
                    t=n1;
                    i++;
                }else{
                    t=n2;
                    j++;
                }
            }else if(i<len1){
                t=nums1[i++];
            }else{
                t=nums2[j++];
            }
            cout<<i+j<<":"<<t<<endl;
        }
        return (len%2?t:(t+lastt)/2.0);
    }
};