题解 | #在两个长度相等的排序数组中找到上中位数#(二分查找寻找)

在两个长度相等的排序数组中找到上中位数

http://www.nowcoder.com/practice/6fbe70f3a51d44fa9395cfc49694404f

class Solution {
public:
    /*
    有序数组 中位数
    二分查找
    1.两个数组中间数相同,合并后,中位数一定是该数
    2.arr1的中位数比arr2 的中位数小则 合并后,中位数一定在arr1的右区间和arr2 的左区间
    3.同理arr2的中位数比arr1 的中位数小则 合并后,中位数一定在arr2的右区间和arr1的左区间
    ps:当时数组长度为偶数时,需要对去除左区间的数组中位数指针移动一位,指向另外一半。
     */
    int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
        int n = arr1.size();
        if(n == 0)return NULL;
        int l1 = 0, r1 = n - 1;
        int l2 = 0, r2 = n - 1;
        int mid1 = 0, mid2 = 0, even = 0;
        while(l1 < r1){
            even = (r1 - l1)%2; // 是否是偶数个
            mid1 = l1 + r1 >> 1; // arr1中位数
            mid2 = l2 + r2 >> 1;// arr2中位数
            if(arr1[mid1] == arr2[mid2]) return arr1[mid1]; // 两个数组中间数相同,合并后,中位数一定是该数
            else if(arr1[mid1] < arr2[mid2]){  // arr1 中位数比 arr2小
                l1 = mid1 + even;
                r2 = mid2;
            }
            else{  // arr2 中位数比 arr1小
                l2 = mid2 + even;
                r1 = mid1;
            }
        }
        return min(arr1[l1], arr2[l2]); // 得到的两个数取中位数,即最小一个就是
    }
};

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
2022-12-24 07:19
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议