题目描述

自我尝试

• 首先，就是两个有序的数组进行遍历，遍历到一半即可。然后求出均值，下述是我的代码。但这明显是有问题的，具体错误的代码如下。计算复杂度太高了，O（n），所以会超时，具体代码如下
• 这说明一个问题，不能逐个遍历，只要遍历就一定有问题的，可以尝试一下对折寻找。

   double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        double numsLeft = 0,numsRight = 0;
        int len = nums1.size() + nums2.size(),index = 0;
        for(int i = 0, j = 0; i <= nums1.size() && j <= nums2.size();){
            if(nums1[i] < nums2[j])
                numsLeft = nums1[i ++] ;
            else
                numsLeft = nums2[j ++ ];
            if(index == len / 2 -1)  numsLeft = numsLeft;
            if(index == len / 2) numsRight = numsLeft;
            index ++;
        }
        if(len % 2 == 2)
            return (numsLeft + numsRight )/ 2;
        else
            return numsRight;
    }

正常做法

• 这里仅仅讲解二分法，只需要注意这里的k是在剩下的元素中，寻找第k小的数字即可

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int tot = nums1.size() + nums2.size();
    if(tot % 2 == 0){
        int left =  find(nums1,0,nums2,0,tot / 2);
        int right = find(nums1,0,nums2,0,tot / 2 + 1);
        return (left + right) / 2.0
    }else{
        return find(nums1,0,nums2,0,tot / 2 + 1);
    }
}

int find(vector<int> nums1,int i,vector<int> nums2,int j,int k){
    /*
     * k表示需要查找的第k个小数字，第一个数字，就表示两个数组在可审查的范围内，都要找第一个元素，所以仅仅比较最小值即可
     */
    // 确保第一个vector的长度是最短的
    if(nums1.size() - i > nums2.size() - j) return find(nums2,j,nums1,i,k);

    // 已经排除了第k-1个元素，剩下的就是第k个元素了，所以仅仅需要比较当前两个数组的最小的元素即可
    if (k == 1){
        if(nums1.size() == i)   return nums2[j];
        else return min(nums1[i],nums2[j]);
    }

    // 第一个数组已经完全检查过了，完全都被排除了，所以，相当于直接在第二个数组中找第k个值
    if (nums1.size() == i) return nums2[j + k - 1];

    // 更新移动数组的下标，进行第二次迭代，这里是将元素进行第二次缩减，然后在进行查找。
    // si和sj是更新之后的新的数组的下标
    int si = min((int)nums1.size(),i + k / 2) ,sj = j + k - k / 2;
    if(nums1[si - 1] > nums2[sj - 1])
        return find(nums1,i,nums2,sj,k - (sj - j));
    else
        return find(nums1,si,nums2,j,k-(si - i));
}

分析总结

• 还是适合中午或者下午做算法题，不然太难受了，一个上午都是晕乎乎的。