[较难]LeetCode-4.寻找两个正序数组的中位数 利用数组扩充和二分法切割思想实现

简介: 题目给定两个大小为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出这两个正序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。你可以假设 nums1 和 nums2 不会同时为空。示例 :nums1 = [1, 3]nums2 = [2]则中位数是 2.0

当我看到题目时,首先想到最简单粗暴的方法是合并数组然后进行排序,但是这样最快也只能达到O(m+n)的级别,不符合题目要求。参考大神的题解后,写一些我的感想。

首先利用数组扩充的思想,将两个数组的和变成偶数,这样方便统一处理。例如,传入的数组为:

nums1:[5,9,10]
nums2:[2,6]

这样两个数组的和是奇数个,我们排好序试试:2,5,6,9,10

这样我们一眼就可以看出来中位数是6,但是对于偶数个的数组计算方法又不一样了。因此,可以把两个数组都变成奇数个,相加后就是偶数个,然后再去求中位数:

#2#5#6#9#10#

想象一下如果数组间存在这些#号,那么不管什么数组一定是奇数个。

在此基础上,我们利用二分法对传入的两个数组进行切割

对nums1来说,在切割时切到了9,因此可以看成:5, 9/9 ,10
对nums2来说,在切割时刚好把两个数分开:2 / 6

做出定义:
LMax1为nums1左侧的最大元素,RMin1为nums1右侧的最小元素
LMax2为nums2左侧的最大元素,RMin2为nums2右侧的最小元素

可以得知目前 LMax1=9 , RMin1=9 , LMax2=2, RMin2 = 6
LMax1≤RMin1 , LMax2≤RMin2 必定成立(题目说明是从小到大排序)

只要满足LMax1≤RMin2, LMax2≤RMin1,我们就可以使用下列公式获得中位数

max(LMax1, LMax2) + min(RMin1, RMin2)) / 2

接下来看看代码

#include <iostream>
#include <vector>
using namespace std;

/**
 * LeetCode
 * 4. 寻找两个正序数组的中位数
 * https://leetcode-cn.com/u/banana798/
 */

#define max(a,b) (((a) > (b)) ? (a) : (b))
#define min(a,b) (((a) < (b)) ? (a) : (b))

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int m = nums2.size();

        if (n > m)  //保证数组1一定最短,这样二分效率最高
        {
            return findMedianSortedArrays(nums2, nums1);
        }

        // Ci 为第i个数组的割,比如C1为2时表示第1个数组只有2个元素。LMaxi为第i个数组割后的左元素。RMini为第i个数组割后的右元素。
        int LMax1, LMax2, RMin1, RMin2, c1, c2, lo = 0, hi = 2 * n;  //我们目前是虚拟加了'#'所以数组1是2*n长度

        while (lo <= hi)   //二分
        {
            c1 = (lo + hi) / 2;  //c1是二分的结果
            //这里C2怎么推导呢,我们可以知道改良后的数组有2m+1+2n+1=2m+2n+2个元素,为偶数个
            //两个基数数组进行切割时会把一个元素切割开,变成2个(切2个变4个,相当于多了2个),因此切割后总数其实是2m+2n+4
            //切割后左边元素整体为c1+1+c2+1
            //则有2m+2n+4-(c1+1+c2+1) = c1+1+c2+1 可推出c2
            c2 = m + n - c1;

            LMax1 = (c1 == 0) ? INT_MIN : nums1[(c1 - 1) / 2];
            RMin1 = (c1 == 2 * n) ? INT_MAX : nums1[c1 / 2];
            LMax2 = (c2 == 0) ? INT_MIN : nums2[(c2 - 1) / 2];
            RMin2 = (c2 == 2 * m) ? INT_MAX : nums2[c2 / 2];

            if (LMax1 > RMin2)
                hi = c1 - 1;
            else if (LMax2 > RMin1)
                lo = c1 + 1;
            else
                break;
        }
        return (max(LMax1, LMax2) + min(RMin1, RMin2)) / 2.0;
    }
};


int main()
{
    // [#5#9#10#]
    vector<int> nums1 = {5,9,10};
    // [#2#6#]
    vector<int> nums2 = {2,6};

    Solution solution;
    cout << solution.findMedianSortedArrays(nums1, nums2);
    return 0;
}

这个方案的难点:

  1. 要清楚数组个数转换为偶数个后如何映射到原数组(即映射关系)
  2. 代码中我详细写了c2变量的推导过程,这个一开始我也没理解

总的来说,这个题很值得我们去研究,如果题目没有要求时间复杂度的话我也不知道还有这种算法。

目录
相关文章
|
1月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
37 0
|
3月前
|
算法
LeetCode第53题最大子数组和
LeetCode第53题"最大子数组和"的解题方法,利用动态规划思想,通过一次遍历数组,维护到当前元素为止的最大子数组和,有效避免了复杂度更高的暴力解法。
LeetCode第53题最大子数组和
LeetCode------找到所有数组中消失的数字(6)【数组】
这篇文章介绍了LeetCode上的"找到所有数组中消失的数字"问题,提供了一种解法,通过两次遍历来找出所有未在数组中出现的数字:第一次遍历将数组中的每个数字对应位置的值增加数组长度,第二次遍历找出所有未被增加的数字,即缺失的数字。
|
26天前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
18 4
|
26天前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
16 0
Leetcode第三十三题(搜索旋转排序数组)
|
26天前
|
算法 C++
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
50 0
|
26天前
|
C++
【LeetCode 12】349.两个数组的交集
【LeetCode 12】349.两个数组的交集
15 0
|
3月前
|
算法
LeetCode第81题搜索旋转排序数组 II
文章讲解了LeetCode第81题"搜索旋转排序数组 II"的解法,通过二分查找算法并加入去重逻辑来解决在旋转且含有重复元素的数组中搜索特定值的问题。
LeetCode第81题搜索旋转排序数组 II
|
3月前
|
算法 索引
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
这篇文章介绍了LeetCode第34题"在排序数组中查找元素的第一个和最后一个位置"的解题方法,通过使用双指针法从数组两端向中间同时查找目标值,有效地找到了目标值的首次和最后一次出现的索引位置。
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
|
3月前
|
算法
LeetCode第33题搜索旋转排序数组
这篇文章介绍了LeetCode第33题"搜索旋转排序数组"的解题方法,通过使用二分查找法并根据数组的有序性质调整搜索范围,实现了时间复杂度为O(log n)的高效搜索算法。
LeetCode第33题搜索旋转排序数组