LeetCode 4. Median of Two Sorted Arrays 二分


给两个排序号的数组,求这两个数组的中位数。题目要求log级复杂度,肯定是二分的思想。

这道题目的难度是Hard,要点如下:
1:对K(第k大数)二分,比如7个数,中位数就是第4大数,那就对4二分。
2:每次去两个数组的前k/2个数,最后一个下标为k/2 - 1,如果有一个数组没有这么多数,例如A,那么说明全部把A的数放到数组B前面,加起来也没有K个,也就是说,第K大数,一定不再B数组的前k/2个,删除掉就好。
3:如果A[k/2 - 1] > B[K/2 - 1]那么说明,第K大数一定也不再B的前k/2个数里,删除掉就好,如此递归k每次都会小k/2,直到k == 1。
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        len1 = nums1.size(), len2 = nums2.size();
        if (len1 == 0 && len2 == 0){
            return 0;
        }
        len = len1 + len2;
        if (len % 2 == 0){
            ans = (dfs(nums1, nums2, 0, 0, len / 2) + dfs(nums1, nums2, 0, 0, len / 2 + 1)) / 2.0;
        }else{
            ans = dfs(nums1, nums2, 0, 0, len / 2 + 1);
        }
        return ans;
    }
     
    double dfs(vector<int>& nums1, vector<int>& nums2, int begin1, int begin2, int k){
        if (begin1 >= len1){
            return nums2[begin2 + k - 1];
        }else if (begin2 >= len2){
            return nums1[begin1 + k - 1];
        }
        
        if (k == 1){
            return min(nums1[begin1], nums2[begin2]);
        }
        
        int mid = (k / 2) - 1;
        int val1 = (begin1 + mid >= len1) ? 0x7fffffff : nums1[begin1 + mid];
        int val2 = (begin2 + mid >= len2) ? 0x7fffffff : nums2[begin2 + mid];

        if (val1 > val2){
            return dfs(nums1, nums2, begin1, begin2 + k / 2, k - k / 2);
        }else{
            return dfs(nums1, nums2, begin1 + k / 2, begin2, k - k / 2);
        }
        
    }               
private:
    int len1, len2, len;
    double ans;
};
已邀请:

要回复问题请先登录注册

返回顶部