寻找两个正序数组的中位数( LeetCode 4 )

一、题目描述

给定两个大小分别为 mn 的正序(从小到大)数组 nums1nums2。请你找出并返回这两个正序数组的 中位数

算法的时间复杂度应该为 O(log (m+n))

示例 1:

输入:nums1 = [1,3], nums2 = [2]
输出:2.00000
解释:合并数组 = [1,2,3] ,中位数 2

示例 2:

输入:nums1 = [1,2], nums2 = [3,4]
输出:2.50000
解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5

示例 3:

输入:nums1 = [0,0], nums2 = [0,0]
输出:0.00000

示例 4:

输入:nums1 = [], nums2 = [1]
输出:1.00000

示例 5:

输入:nums1 = [2], nums2 = []
输出:2.00000

提示:

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -10^6 <= nums1[i], nums2[i] <= 10^6

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 寻找两个正序数组的中位数(4):https://leetcode-cn.com/problems/median-of-two-sorted-arrays/submissions/
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {

        // 中位数的概念:将一个集合划分为两个长度相等的子集,其中一个子集中的元素总是大于另一个子集中的元素
        // 由于数组的长度有两种情况:奇数、偶数
        // 奇数组: [2 3 5] 对应的中位数为 3
        // 偶数组: [1 4 7 9] 对应的中位数为 ( 4 + 7 ) / 2 = 5.5


        // 获取 nums1 的长度
        int n = nums1.length;

        // 获取 nums2 的长度
        int m = nums2.length;

        if( n > m){
            // 通过这个方法,可以将 nums1 和 nums2 进行一个交换操作,确保 nums1 的长度一定小于 nums2
            return findMedianSortedArrays(nums2,nums1);
        }

        // nums1、nums2 均为有序数组
        // 如果将有序数组切割分成两部分,那么切的那个位置的左侧为左边最大值,切的那个位置的右侧为右边最小值
        //      |
        // [1 4 | 7 9] 
        //      |
        // 比如 4 就是左部分的最大值,7 就是右部分的最小值

        // 设置两个变量 Cut1、Cut2 方便切割 nums1、nums2
        // 不断的挪动 Cut1 和 Cut2 切的位置,如果说 Cut1、Cut2 找到了合适的位置进行切割
        // 1、 ( nums1 的左部分 + nums2 的左部分 )个数 = ( nums1 的右部分 + nums2 的右部分 )个数】
        // 2、( nums1 的左部分 + nums2 的左部分 )最大数 <= ( nums1 的右部分 + nums2 的右部分 )最小数
        // 那么也就找到了中位数

        // 一开始 Cut1 为 0
        int Cut1 = 0;

        // 一开始 Cut2 为 0
        int Cut2 = 0;

        // nums1、nums2 均为有序数组
        // 显然,LMax1 <= RMin1,LMax2 <= RMin2

        // LMax1 表示 nums1 被 Cut1 切割后,左部分的最大值
        int LMax1 = 0;

        // LMax2 表示 nums2 被 Cut2 切割后,左部分的最大值
        int LMax2 = 0;

        // RMin1 表示 nums1 被 Cut1 切割后,右部分的最小值
        int RMin1 = 0;

        // RMin2 表示 nums2 被 Cut2 切割后,右部分的最小值
        int RMin2 = 0;

        // 一开始 Cut1 = 0,Cut2 = 0 ,也就是说 nums1 的左部分 0 个元素, nums2 的左部分 0 个元素
        // 因此需要挪动 Cut1、Cut2 的位置,使得 ( nums1 的左部分 + nums2 的左部分 )个数 = ( nums1 的右部分 + nums2 的右部分 )个数

        // 所以,一开始直接把 Cut1 挪到 nums1 的中间位置进行切割,把 Cut2 挪到 nums2 的中间位置进行切割
        // 如果 LMax1 <= RMin2,LMax2 <= RMin1
        // 又由于 LMax1 <= RMin1,LMax2 <= RMin2
        // 意味着
        // 1、( nums1 的左部分 + nums2 的左部分 )个数 = ( nums1 的右部分 + nums2 的右部分 )个数
        // 2、( nums1 的左部分 + nums2 的左部分 )最大数 <= ( nums1 的右部分 + nums2 的右部分 )最小数

        // 当发现 LMax1 > RMin2 时,说明 Cut1 切的位置不对,左边的元素太多了,需要把一些元素挪到右边来,这样才能减小 LMax1 的值
        // 所以  Cut1 的值减小了
        // 而因为 ( nums1 的左部分 + nums2 的左部分 )个数 = Cut1 + Cut2
        // Cut2 变大了,也就是说可以通过 Cut1 的位置找到 Cut2 的位置

        // 由于 m + n 可能为奇数, 也可能为偶数,为了方便统一处理,这里加入一个技巧
        // 在数组的 开头、结尾、数字直接加入一个 “#”
        // 这样 nums2 的长度 m 变成了 2m + 1
        // 这样 nums1 的长度 n 变成了 2n + 1
        // 两数之和变成了 2m + 2n + 2,恒为偶数
        // 比如 [ 1 、3 、5 、7 ] 变成了 [ #、 1 、# 、3 、 # 、5  、 # 、7 、# ]
        // 比如 [ 2 、4 、6 ] 变成了 [ #、 2 、# 、4 、 # 、6  、 #  ]
        // 因此,每个位置的下标位置发生了改变,但可以通过 /2 得到原来元素的位置:
        // 比如 1,原来在 0 位,现在是 1 位,1 / 2 = 0
        // 比如 3,原来在 1 位,现在是 3 位,3 / 2 = 1
        // 比如 6,原来在 2 位,现在是 5 位,5 / 2 = 2

        // 此时,LMax1 = ( Cut1 - 1 ) / 2 位置上的元素
        // RMin1 = Cut1 / 2 位置上的元素

        // 接下来,开始找 Cut1 和 Cut2 的位置了

        // left 为 nums1 最左侧的元素,可以获取到
        int left = 0;

        // 添加了 “#” 后,nums1 的长度 n 变成了 2n + 1
        // right 为 nums1 最右侧的元素,可以获取到
        int right = 2 * n ; 

        // 在 while 循环里面,left 不断的 ++,而 right 不断的 --
        // 当 [ left , right ] 这个区间不存在元素的时候,才跳出 while 循环,也就是当 left > right 时跳出循环
        // 即当 left = right + 1 时,搜索区间没有元素了
        // 由于 left 和 right 相遇的时候指向同一个元素,这个元素是存在于 [ left , right] 区间,这个区间就一个元素
        // 所以此时 while 循环的判断可以使用等号
        while( left <= right){

            // Cut1 切在 nums1 的中间位置
            Cut1 = left + ( right - left ) / 2;

            // ( nums1 的左部分 + nums2 的左部分 )个数 = m + n
            // 所以 Cut2 = m + n - Cut1
            Cut2 = m + n - Cut1;

            // 注意几种边界情况

            // 1、nums1 左部分没有元素,全部都在右部分,并且元素值都比中值大
            // 所以,中值在 nums2 中,这里就可以假定 LMax1 = INT_MIN
            if( Cut1 == 0 ){
                LMax1 = Integer.MIN_VALUE;
            }else{
                // 否则 LMax1 切割位置的左边元素
                LMax1 = nums1[ (Cut1 - 1) / 2 ];
            }

            // 2、nums1 右部分没有元素,全部都在左部分,并且元素值都比中值小
            // 所以,中值在 nums2 中,这里就可以假定 RMin1 = MAX_VALUE
            if( Cut1 == 2 * n){
                RMin1 = Integer.MAX_VALUE;
            }else{
                // 否则 RMin1 切割位置的右边元素
                RMin1 = nums1[ Cut1  / 2 ];
            }

            // 3、nums2 左部分没有元素,全部都在右部分,并且元素值都比中值大
            // 所以,中值在 nums1 中,这里就可以假定 LMax2 = INT_MIN
            if( Cut2 == 0){
                LMax2 = Integer.MIN_VALUE;
            }else{
                // 否则 LMax2 切割位置的左边元素
                LMax2 = nums2[ (Cut2 - 1) / 2 ];
            }

            // 2、nums2 右部分没有元素,全部都在左部分,并且元素值都比中值小
            // 所以,中值在 nums1 中,这里就可以假定 RMin2 = MAX_VALUE
            if( Cut2 == 2 * m){
                RMin2 = Integer.MAX_VALUE;
            }else{
                // 否则 RMin2 切割位置的右边元素
                RMin2 = nums2[ Cut2  / 2 ];
            }

            // LMax1 > RMin2
            // 说明 Cut1 切的位置不对,左边的元素太多了,需要把一些元素挪到右边来,这样才能减小 LMax1 
            // Cut1 切的位置向左边挪一些
            if( LMax1 > RMin2 ){
                // 也就是说缩小之后的区间最右侧位置为 Cut1 - 1
                right = Cut1 - 1;

            // LMax2 > RMin1
            // 说明 Cut1 切的位置不对,左边的元素太少了,需要把一些元素挪到左边来,这样才能增大 RMin1  
            // Cut1 切的位置向右边挪一些
            }else if( LMax2 > RMin1 ){
                // 也就是说缩小之后的区间最左侧位置为 Cut1 + 1
                left = Cut1 + 1;
            }else{
                // 否则就是说明切的位置合适,不用再找其它位置了
                // 1、( nums1 的左部分 + nums2 的左部分 )个数 = ( nums1 的右部分 + nums2 的右部分 )个数
                // 2、( nums1 的左部分 + nums2 的左部分 )最大数 <= ( nums1 的右部分 + nums2 的右部分 )最小数
                break;
            }

        }

        // 那么再获取 LMax1 和 LMax2 较大值 + RMin1 和 RMin2 的较小值
        // 两者相加除以 2 就是结果
        return (Math.max(LMax1,LMax2) + Math.min(RMin1,RMin2)) / 2.0;

    }
}

2、C++ 代码

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者:程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 寻找两个正序数组的中位数(4):https://leetcode-cn.com/problems/median-of-two-sorted-arrays/submissions/
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:

        # 中位数的概念:将一个集合划分为两个长度相等的子集,其中一个子集中的元素总是大于另一个子集中的元素
        # 由于数组的长度有两种情况:奇数、偶数
        # 奇数组: [2 3 5] 对应的中位数为 3
        # 偶数组: [1 4 7 9] 对应的中位数为 ( 4 + 7 ) / 2 = 5.5


        # 获取 nums1 的长度
        n = len(nums1)

        # 获取 nums2 的长度
        m = len(nums2)

        if n > m :
            # 通过这个方法,可以将 nums1 和 nums2 进行一个交换操作,确保 nums1 的长度一定小于 nums2
            return self.findMedianSortedArrays(nums2,nums1)


        # nums1、nums2 均为有序数组
        # 如果将有序数组切割分成两部分,那么切的那个位置的左侧为左边最大值,切的那个位置的右侧为右边最小值
        #      |
        # [1 4 | 7 9] 
        #      |
        # 比如 4 就是左部分的最大值,7 就是右部分的最小值

        # 设置两个变量 Cut1、Cut2 方便切割 nums1、nums2
        # 不断的挪动 Cut1 和 Cut2 切的位置,如果说 Cut1、Cut2 找到了合适的位置进行切割
        # 1、 ( nums1 的左部分 + nums2 的左部分 )个数 = ( nums1 的右部分 + nums2 的右部分 )个数】
        # 2、( nums1 的左部分 + nums2 的左部分 )最大数 <= ( nums1 的右部分 + nums2 的右部分 )最小数
        # 那么也就找到了中位数

        # 一开始 Cut1 为 0
        Cut1 = 0

        # 一开始 Cut2 为 0
        Cut2 = 0

        # nums1、nums2 均为有序数组
        # 显然,LMax1 <= RMin1,LMax2 <= RMin2

        # LMax1 表示 nums1 被 Cut1 切割后,左部分的最大值
        LMax1 = 0

        # LMax2 表示 nums2 被 Cut2 切割后,左部分的最大值
        LMax2 = 0

        # RMin1 表示 nums1 被 Cut1 切割后,右部分的最小值
        RMin1 = 0

        # RMin2 表示 nums2 被 Cut2 切割后,右部分的最小值
        RMin2 = 0

        # 一开始 Cut1 = 0,Cut2 = 0 ,也就是说 nums1 的左部分 0 个元素, nums2 的左部分 0 个元素
        # 因此需要挪动 Cut1、Cut2 的位置,使得 ( nums1 的左部分 + nums2 的左部分 )个数 = ( nums1 的右部分 + nums2 的右部分 )个数

        # 所以,一开始直接把 Cut1 挪到 nums1 的中间位置进行切割,把 Cut2 挪到 nums2 的中间位置进行切割
        # 如果 LMax1 <= RMin2,LMax2 <= RMin1
        # 又由于 LMax1 <= RMin1,LMax2 <= RMin2
        # 意味着
        # 1、( nums1 的左部分 + nums2 的左部分 )个数 = ( nums1 的右部分 + nums2 的右部分 )个数
        # 2、( nums1 的左部分 + nums2 的左部分 )最大数 <= ( nums1 的右部分 + nums2 的右部分 )最小数

        # 当发现 LMax1 > RMin2 时,说明 Cut1 切的位置不对,左边的元素太多了,需要把一些元素挪到右边来,这样才能减小 LMax1 的值
        # 所以  Cut1 的值减小了
        # 而因为 ( nums1 的左部分 + nums2 的左部分 )个数 = Cut1 + Cut2
        # Cut2 变大了,也就是说可以通过 Cut1 的位置找到 Cut2 的位置

        # 由于 m + n 可能为奇数, 也可能为偶数,为了方便统一处理,这里加入一个技巧
        # 在数组的 开头、结尾、数字直接加入一个 “#”
        # 这样 nums2 的长度 m 变成了 2m + 1
        # 这样 nums1 的长度 n 变成了 2n + 1
        # 两数之和变成了 2m + 2n + 2,恒为偶数
        # 比如 [ 1 、3 、5 、7 ] 变成了 [ #、 1 、# 、3 、 # 、5  、 # 、7 、# ]
        # 比如 [ 2 、4 、6 ] 变成了 [ #、 2 、# 、4 、 # 、6  、 #  ]
        # 因此,每个位置的下标位置发生了改变,但可以通过 /2 得到原来元素的位置:
        # 比如 1,原来在 0 位,现在是 1 位,1 / 2 = 0
        # 比如 3,原来在 1 位,现在是 3 位,3 / 2 = 1
        # 比如 6,原来在 2 位,现在是 5 位,5 / 2 = 2

        # 此时,LMax1 = ( Cut1 - 1 ) / 2 位置上的元素
        # RMin1 = Cut1 / 2 位置上的元素

        # 接下来,开始找 Cut1 和 Cut2 的位置了

        # left 为 nums1 最左侧的元素,可以获取到
        left = 0

        # 添加了 “#” 后,nums1 的长度 n 变成了 2n + 1
        # right 为 nums1 最右侧的元素,可以获取到
        right = 2 * n  

        # 在 while 循环里面,left 不断的 ++,而 right 不断的 --
        # 当 [ left , right ] 这个区间不存在元素的时候,才跳出 while 循环,也就是当 left > right 时跳出循环
        # 即当 left = right + 1 时,搜索区间没有元素了
        # 由于 left 和 right 相遇的时候指向同一个元素,这个元素是存在于 [ left , right] 区间,这个区间就一个元素
        # 所以此时 while 循环的判断可以使用等号
        while left <= right :

            # Cut1 切在 nums1 的中间位置
            Cut1 = left + ( right - left ) // 2

            # ( nums1 的左部分 + nums2 的左部分 )个数 = m + n
            # 所以 Cut2 = m + n - Cut1
            Cut2 = m + n - Cut1

            # 注意几种边界情况

            # 1、nums1 左部分没有元素,全部都在右部分,并且元素值都比中值大
            # 所以,中值在 nums2 中,这里就可以假定 LMax1 = INT_MIN
            if Cut1 == 0 :
                LMax1 = -1000001
            else :
                # 否则 LMax1 切割位置的左边元素
                LMax1 = nums1[ (Cut1 - 1) // 2 ]


            # 2、nums1 右部分没有元素,全部都在左部分,并且元素值都比中值小
            # 所以,中值在 nums2 中,这里就可以假定 RMin1 = MAX_VALUE
            if Cut1 == 2 * n :
                RMin1 = 1000001
            else:
                # 否则 RMin1 切割位置的右边元素
                RMin1 = nums1[ Cut1  // 2 ] 


            # 3、nums2 左部分没有元素,全部都在右部分,并且元素值都比中值大
            # 所以,中值在 nums1 中,这里就可以假定 LMax2 = INT_MIN
            if Cut2 == 0 :
                LMax2 = -1000001
            else:
                # 否则 LMax2 切割位置的左边元素
                LMax2 = nums2[ (Cut2 - 1) // 2 ]


            # 2、nums2 右部分没有元素,全部都在左部分,并且元素值都比中值小
            # 所以,中值在 nums1 中,这里就可以假定 RMin2 = MAX_VALUE
            if Cut2 == 2 * m :
                RMin2 = 1000001
            else: 
                # 否则 RMin2 切割位置的右边元素
                RMin2 = nums2[ Cut2  // 2 ]


            # LMax1 > RMin2
            # 说明 Cut1 切的位置不对,左边的元素太多了,需要把一些元素挪到右边来,这样才能减小 LMax1 
            # Cut1 切的位置向左边挪一些
            if  LMax1 > RMin2 :
                # 也就是说缩小之后的区间最右侧位置为 Cut1 - 1
                right = Cut1 - 1

            # LMax2 > RMin1
            # 说明 Cut1 切的位置不对,左边的元素太少了,需要把一些元素挪到左边来,这样才能增大 RMin1  
            # Cut1 切的位置向右边挪一些
            elif  LMax2 > RMin1 :
                # 也就是说缩小之后的区间最左侧位置为 Cut1 + 1
                left = Cut1 + 1
            else:
                # 否则就是说明切的位置合适,不用再找其它位置了
                # 1、( nums1 的左部分 + nums2 的左部分 )个数 = ( nums1 的右部分 + nums2 的右部分 )个数
                # 2、( nums1 的左部分 + nums2 的左部分 )最大数 <= ( nums1 的右部分 + nums2 的右部分 )最小数
                break

        # 那么再获取 LMax1 和 LMax2 较大值 + RMin1 和 RMin2 的较小值
        # 两者相加除以 2 就是结果
        return (max(LMax1,LMax2) + min(RMin1,RMin2)) / 2.0

四、动画理解(没有声音)

发表评论

邮箱地址不会被公开。 必填项已用*标注