【重点!!!】【二分查找】4.寻找两个正序数组的中位数

题目

最佳解法:二分查找

在这里插入图片描述
在这里插入图片描述

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1
        m, n = len(nums1), len(nums2)
        imin, imax, half = 0, m, (m+n+1) // 2
        while imin <= imax:
            i = (imin + imax) // 2 # nums1分割线左侧元素数量
            j = half - i           # nums2分割线左侧元素数量
            if i < m and nums2[j-1] > nums1[i]: # i太小, 需要增大
                imin += 1
            elif i > 0 and nums1[i-1] > nums2[j]: # i太大,需要降低
                imax -= 1
            else:
                nums1_left_max = -inf if i == 0 else nums1[i-1]
                nums1_right_min = inf if i == m else nums1[i]
                nums2_left_max = -inf if j == 0 else nums2[j-1]
                nums2_right_min = inf if j == n else nums2[j]
                if (m + n) % 2 == 1:
                    return max(nums1_left_max, nums2_left_max)
                else:
                    return (max(nums1_left_max, nums2_left_max) + min(nums1_right_min, nums2_right_min)) / 2.0

法1:二分查找(最优解法)

时间复杂度:O(logMin(m, n)),空间复杂度:O(1)。
同时看这两种解法及其注释!!!
视频讲解:https://www.bilibili.com/video/BV1Xv411z76J/?spm_id_from=333.337.search-card.all.click&vd_source=af30aa36f473ad5a8ffdcc06e213d1f6
在这里插入图片描述

Python

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1
        m, n = len(nums1), len(nums2)
        total = (m + n + 1) // 2
        # 在nums1的区间[0, m]里查找恰当的分割线
        # 使得nums1[i - 1] ≤ nums2[j] && nums2[j - 1] ≤ nums1[i]
        left, right = 0, m # [a, b)开闭区间
        while left < right:
            nums1_left = (left + right + 1) // 2        # nums1分割线左边元素数量
            nums2_left = total - nums1_left             # nums2分割线左边元素数量
            if nums1[nums1_left-1] > nums2[nums2_left]: # 分割线太靠右了,需要往左移动
                right = nums1_left-1
            else:
                left = nums1_left
        i, j = left, total - left
        nums1_left_max = -inf if i == 0 else nums1[i-1]
        nums1_right_min = inf if i == m else nums1[i]
        nums2_left_max = -inf if j == 0 else nums2[j-1]
        nums2_right_min = inf if j == n else nums2[j]
        if (m + n) % 2 == 1:
            return max(nums1_left_max, nums2_left_max)
        else:
            return (max(nums1_left_max, nums2_left_max) + min(nums1_right_min, nums2_right_min)) / 2.0

Java

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            int[] tmp = nums1;
            nums1 = nums2;
            nums2 = tmp;
        }
        int m = nums1.length, n = nums2.length;
        // 在nums1的区间[0, m]里查找恰当的分割线
        // 使得nums1[i - 1] ≤ nums2[j] && nums2[j - 1] ≤ nums1[i]

        int totalLeft = (m + n + 1) / 2; // 左 ≥ 右
        int left = 0, right = m; // [left, right)是闭开区间
        while (left < right) {
            int nums1Left = (left + right + 1) / 2; // 是指的nums1分割线左侧元素个数(左 ≥ 右), 对应索引是nums1Left - 1
            int nums2Left = totalLeft - nums1Left;  // 是指的nums2分割线左侧元素个数(左 ≥ 右), 对应索引是nums2Left - 1
            if (nums1[nums1Left - 1] > nums2[nums2Left]) { // nums1的分割线太靠右,需要往左移
                right = nums1Left - 1; // right是取不到的边界, 下次迭代索引nums1Left - 1肯定取不到,故设置right = nums1Left - 1
            } else { // 这里并未直接判断nums2[nums2Left - 1]与nums1[nums1Left]的关系, 故使得nums1[nums1Left]尽量大
                left = nums1Left;      // left是可取到的边界,  下次迭代索引可能取到nums1Left,故设置left = nums1Left
            }
        }
        int i = left, j = totalLeft - left;
        int nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
        int nums1RightMin = i == m ? Integer.MAX_VALUE : nums1[i];
        int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
        int nums2RightMin = j == n ? Integer.MAX_VALUE : nums2[j];
        int leftMax = Math.max(nums1LeftMax, nums2LeftMax);
        int rightMin = Math.min(nums1RightMin, nums2RightMin);
        if ((m + n) % 2 == 1) {
            return (double) leftMax;
        } else {
            return ((double) leftMax + (double) rightMin) / 2.0;
        }
    }
}
<think>嗯,用户让我讲解“寻找两个序数中位数”这道题,用C++,而且要最简单易懂的方法。我得先回忆一下这个问题应该怎么解决。 首先,题目是说有两个已经排好序的数,我要找到它们合并后的中位数。那中位数的话,如果是合并后数长度是奇数,就是中间那个数;如果是偶数,就是中间两个数的平均值。对吧? 那问题来了,怎么高效地找到这个中位数呢?如果直接合并两个,虽然简单,但时间复杂度是O(m+n),可能不符合题目要求的O(log(m+n))。不过用户可能刚开始学,可能更希望先理解基础的方法,再优化?或者题目是否允许O(m+n)的解法? 不过用户要求的是最简单容易理解和记忆的方法,那可能先给出合并数的方法会更合适。虽然时间复杂度高,但容易理解,适合新手。而且如果两个长度不大,这种方法也适用。 那具体步骤应该怎么做呢?首先,我需要合并两个序数。合并的方法可以用双指针,分别指向两个的起始位置,比较大小,依次将较小的元素放入新数,直到所有元素都加入。这和归并排序的合并过程是一样的。 合并之后,判断总长度的奇偶性。如果是奇数,取中间的那个;偶数的话,取中间两个的平均值。这一步应该不难。 那用C++的话,代码应该怎么写呢?首先,合并两个。可以用一个vector来存储合并后的结果。然后两个指针i和j,初始为0,然后循环比较nums1[i]和nums2[j],较小的放入新数,并移动对应的指针。当其中一个数遍历完后,把另一个剩下的元素全部加入。 比如,假设nums1是[1,3],nums2是[2]。合并后是[1,2,3],长度3,中位数是2。如果是nums1是[1,2],nums2是[3,4],合并后是[1,2,3,4],中位数是(2+3)/2=2.5。 那代码的大致结构应该是这样的。需要注意的是,处理合并后的数为空的情况吗?题目说两个都是序的,但可能其中一个或两个为空。比如其中一个数为空,直接处理另一个数中位数。 那在代码中,合并的时候要考虑两个是否已经遍历完。比如,当i或者j已经到达各自的数末尾时,就将剩下的元素全部添加进去。 然后计算中位数部分,判断合并后的数长度是奇数还是偶数。如果是奇数,直接取中间位置;如果是偶数,取中间两个数的平均值。 那这样写出来的代码虽然时间复杂度高,但确实直观易懂,适合理解和记忆。对于刚接触这道题的人来说,先掌握这种方法,后续再学习更高效的二分查找方法可能更合适。 那现在考虑测试例子是否确。比如例子1:nums1 = [1,3], nums2 = [2],合并后数是[1,2,3],长度3,中位数是2。代码应该返回确结果。另一个例子,nums1 = [1,2], nums2 = [3,4],合并后的数是[1,2,3,4],中位数是2.5,代码应该能确计算。 那这样的代码是否存在问题?可能的空间复杂度是O(m+n),因为需要合并后的数。但对于题目来说,如果m和n都不大,这应该可以接受。不过题目可能期望更优的解法,但用户要求的是简单方法,所以应该没问题。 那现在写出代码的话,大致步骤是: 1. 合并两个,使用双指针。 2. 计算合并后的数长度,判断奇偶。 3. 返回中位数。 那现在需要处理的情况,比如其中一个数为空的情况。例如nums1为空,那么合并后的数就是nums2。或者其中一个数的所有元素都小于另一个数,比如nums1=[1,2,3], nums2=[4,5,6],合并后的数就是两者的拼接。 那代码的结构: vector<int> merged; int i=0, j=0; while (i < m && j < n) { if (nums1[i] < nums2[j]) { merged.push_back(nums1[i++]); } else { merged.push_back(nums2[j++]); } } // 处理剩下的元素 while (i < m) merged.push_back(nums1[i++]); while (j < n) merged.push_back(nums2[j++]); 然后计算中位数。比如,size = merged.size(); if (size % 2 ==1) return merged[size/2]; else return (merged[size/2-1] + merged[size/2])/2.0; 这里需要注意返回类型是否为double。题目中的中位数可能需要浮点数。例如上面的第二个例子,返回的是2.5,所以用double类型。 在C++中,如果两个整数相加后除以2.0,结果会是double。比如(2+3)/2.0=2.5。 综上,这样的代码应该能解决问题。虽然时间复杂度是O(m+n),但容易理解和记忆,适合初学。 可能的测试案例: 测试案例1: nums1 = [1,3], nums2 = [2] 合并后数为[1,2,3],中位数2.0 测试案例2: nums1 = [1,2], nums2 = [3,4] 合并后数为[1,2,3,4],中位数2.5 测试案例3: nums1为空,nums2 = [1],中位数1.0 测试案例4: nums1 = [0,0], nums2 = [0,0],合并后四个0,中位数0.0 这些情况都应该被确处理。 所以,总结思路:合并数,找中间的数。这个方法虽然不高效,但容易理解,适合作为初学者的解法。</think>### 问题解析 题目要求找出两个序数合并后的中位数中位数的定义为: - 若合并后数长度为奇数,取中间那个数 - 若为偶数,取中间两个数的平均值 ### 直观解法思路 使用归并排序的合并思路,将两个序数合并成一个有序数,再直接取中间值。这种方法虽然时间复杂度为 O(m+n),但思路简单,便于理解和记忆。 ### 代码实现 ```cpp #include <vector> using namespace std; double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { vector<int> merged; int i = 0, j = 0; int m = nums1.size(), n = nums2.size(); // 合并两个序数 while (i < m && j < n) { if (nums1[i] < nums2[j]) { merged.push_back(nums1[i++]); } else { merged.push_back(nums2[j++]); } } // 处理剩余元素 while (i < m) merged.push_back(nums1[i++]); while (j < n) merged.push_back(nums2[j++]); // 计算中位数 int size = merged.size(); if (size % 2 == 1) { return merged[size/2]; } else { return (merged[size/2 - 1] + merged[size/2]) / 2.0; } } ``` ### 代码解析 1. **合并数**:使用双指针法合并两个序数,与归并排序的合并过程一致 2. **处理剩余元素**:当一个数遍历完后,直接将另一个数剩余元素加入 3. **计算中位数**: - 奇数长度:直接返回中间元素 `merged[size/2]` - 偶数长度:返回中间两个元素的平均值 `(merged[k-1]+merged[k])/2.0` ### 复杂度分析 - 时间复杂度:O(m+n)(需要遍历两个所有元素) - 空间复杂度:O(m+n)(需要存储合并后的数) ### 示例验证 例1:nums1 = [1,3], nums2 = [2] ``` 合并后数 = [1,2,3] 中位数 = 2.0 ``` 例2:nums1 = [1,2], nums2 = [3,4] ``` 合并后数 = [1,2,3,4] 中位数 = (2+3)/2 = 2.5 ``` 这种方法虽然效率不是最优,但代码结构清晰,非常适合帮助理解问题本质。后续可以在此基础上学习更高效的二分查找解法。
评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值