leetcode Median of Two Sorted Arrays

ゞ浴缸里的玫瑰 2022-08-05 00:59 160阅读 0赞

## 题目： ##

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/][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;
        }
    };

[https_leetcode.com_problems_median-of-two-sorted-arrays]: https://leetcode.com/problems/median-of-two-sorted-arrays/