首页 > itarticle > leetcode median of two sorted arrays

leetcode median of two sorted arrays

admin 11月 11, 2020 0

文章目录

tips

median, 找中位数
奇数数组中位数，a[n/2 + 1]
偶数数组中位数，(a[n/2]+a[n/2+1])/2.0
化简为两个有序数组找第k大元素问题，普通解法O(m+n)，用递归可以达到O(log(m+n))

class  {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int total = nums1.size() + nums2.size();
        if(total & 1) {
            return findKth(nums1, nums2, 0, 0, total / 2 + 1);
        }else {//not odd
            return (findKth(nums1, nums2, 0, 0, total / 2) + findKth(nums1, nums2, 0, 0, total / 2 + 1)) / 2.0;
        }
    }
    double findKth(vector<int>& nums1, vector<int>& nums2, int nums1_start, int nums2_start, int k) {
        if(nums1_start >= nums1.size()) {
            return nums2[nums2_start + k - 1];
        }
        if(nums2_start >= nums2.size()) {
            return nums1[nums1_start + k - 1];
        }
        if(k == 1) return min(nums1[nums1_start], nums2[nums2_start]);

        int nums1_key = nums1_start + k / 2  - 1>= nums1.size() ? INT_MAX : nums1[nums1_start + k / 2 - 1];
        int nums2_key = nums2_start + k / 2  - 1>= nums2.size() ? INT_MAX : nums2[nums2_start + k / 2 - 1];
        
        if(nums1_key < nums2_key) {
            return findKth(nums1, nums2, nums1_start + k / 2, nums2_start, k - k / 2);
        }else {
            return findKth(nums1, nums2, nums1_start, nums2_start + k / 2, k - k / 2);
        }
    }
};