leetcode Median of Two Sorted Arrays-蒲公英云

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)).
题目来源：https://leetcode.com/problems/median-of-two-sorted-arrays/

分析：

在两个排好序的数组里面找中位数。中位数的定义是，如果一共奇数个数，则排序后中间的数便是中位数；如果一共偶数个数，则排序后中间的两个数便是中位数。既然两个数组已经排好序，则可以利用merge的思路对两个数组进行排序。当然也可以不存放排序的结果，只记录下排到第几个了就行，当cnt计数器计到中位数的位置了，就得出结果了。

代码：

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n1 = nums1.size();
        int n2 = nums2.size();
        int med = (n1 + n2)/2;
        if((n1+n2)%2 == 1)
            med += 1;
        int p1 = 0, p2 = 0, tmp = 0, cnt = 0;
        while(p1 < n1 && p2 < n2){
            if(nums1[p1] < nums2[p2]){
                tmp = nums1[p1++];
            }
            else{
                tmp = nums2[p2++];
            }
            cnt++;
            if(cnt == med){
                if((n1+n2)%2 == 1)
                    return (double)tmp;
                else{
                    double next;
                    if(p1 >= n1)//针对偶数个数字，中间的两个数一个在结尾另一个在开头。
                        next = nums2[p2];
                    else if(p2 >= n2)
                        next = nums1[p1];
                    else
                        next = nums1[p1] < nums2[p2] ? nums1[p1] : nums2[p2];
                    return double(next + tmp) / 2;
                }
            }
        }
        while(p1 < n1){
            tmp = nums1[p1++];
            cnt++;
            if(cnt == med){
                if((n1+n2)%2 == 1)
                    return tmp;
                else
                    return (double)(tmp + nums1[p1]) / 2;
            }
        }
        while(p2 < n2){
            tmp = nums2[p2++];
            cnt++;
            if(cnt == med){
                if((n1+n2)%2 == 1)
                    return tmp;
                else
                    return (double)(tmp + nums2[p2]) / 2;
            }
        }
        return 0;
    }
};