C/C++描述 LeetCode 4. 寻找两个正序数组的中位数

C/C++描述 LeetCode 4. 寻找两个正序数组的中位数

  大家好，我叫亓官劼（qí guān jié ），在CSDN中记录学习的点滴历程，时光荏苒，未来可期，加油~博主目前仅在CSDN中写博客，唯一博客更新的地址为：亓官劼的博客

本文原创为亓官劼，请大家支持原创，部分平台一直在恶意盗取博主的文章！！！

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。

请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

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

则中位数是 2.0

示例 2:

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

则中位数是 (2 + 3)/2 = 2.5

题解

题目中要求算法的时间复杂度为$ O(log(m+n)) $,所以这里不能直接暴力，由于是已经排序好的两个数组，我们可以使用二分法。两个数组的二分这里我们可以再进行再一次的转化，将寻找中位数转化为寻找第k小的数，如果总长度为奇数，那么中位数就是第(len+1)/2的数，如果总长度为偶数，那么中位数就为(len/2 + len/2+1) /2.0，然后我们使用这个思想进行算法实现。

class Solution {
   
public:
    int fintK(vector<int>& nums1, vector<int>& nums2, int k){
   
        int len1 = nums1.size();
        int len2 = nums2.size();
        int index1 = 0;
        int index2 = 0;
        while(true){
   
            // 当运行到右边界时
            if(index1 == len1){
   
                // 返回nums2当前index2+k个数
                return nums2[index2 + k - 1];
            }
            if(index2 == len2){
   
                return nums1[index1 + k - 1];
            }
            if(k == 1)
                return min(nums1[index1],nums2[index2]);
            int newIndex1 = min(index1 + k / 2 - 1, len1 - 1);
            int newIndex2 = min(index2 + k / 2 - 1, len2 - 1);
            int pivot1 = nums1[newIndex1];
            int pivot2 = nums2[newIndex2];
            if (pivot1 <= pivot2) {
   
                k -= newIndex1 - index1 + 1;
                index1 = newIndex1 + 1;
            }
            else {
   
                k -= newIndex2 - index2 + 1;
                index2 = newIndex2 + 1;
            }
        }
    }
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
   
        // 转换为找第K小的数，当len为偶数时，找len/2 + len/2+1两个数，当len为奇数时，找第len/2的数
        int len = nums1.size() + nums2.size();
        if(len%2 == 0){
   
            //当len为偶数时，找第len/2 + len/2+1两个数,中位数为两个数/2.0
            return ((fintK(nums1,nums2,len/2) + fintK(nums1,nums2,len/2+1) )/2.0 );
        }else{
   
            //当len为奇数时，找第(len+1)/2的数
            return fintK(nums1,nums2,(len+1)/2);
        }

    }
};