当前位置：首页 > news >正文

[刷题][lettcode困难]4.寻找两个正序数组的中位数

news 2025/5/5 14:12:49

原题链接

4. 寻找两个正序数组的中位数 - 力扣（LeetCode）

标签 : 数组,二分查找,分治

解法一:暴力遍历

虽然题目强制要求复杂度,但是经过测试直接暴力求解也是可以过的

思路:构建一个新数组tmp,将nums1,nums2中的元素加入到tmp中,整个进行一个排序,让后找中位数就行,因为涉及到排序所以时间复杂度为o((m+n) * log(m + n))

时间复杂度 : o((m+n) * log(m + n))

这个暴力解法可以再优化一点点,因为nums1,nums2本身都是有序的,如果按归并排序的方法合并原数组,可以不用排序,这样的话时间复杂度会降到o(m+n)

这两种暴力算法显然不是题目所期望的解法

class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {vector<int> tmp;for(auto e : nums1) tmp.push_back(e);for(auto e : nums2) tmp.push_back(e);sort(tmp.begin(),tmp.end());if(tmp.size() % 2 == 0){double t = tmp[tmp.size()/2] + tmp[tmp.size()/2 -1];return t / 2;}else{return tmp[tmp.size()/2];}}
};

解法二:去值法

名字是我自己编的,力扣官方叫二分查找法,我觉得不是那么得贴切,修改了一下,不过最终思路是一样的

解法二:一周目

已经知道 nums1 长度为n,nums2 长度为 m

        如果 m + n 为奇数

        我们把中位数理解为合并数组的第 (m + n + 1)/2 小的值(为什么不是第(m+n)/2大的值呢,理论上来说也可以是第k大的值,但是从右往左进行运算并不符合普通人的生活习惯,而且要花心思去考虑烦人的下标问题)

        如果m + n 为偶数

        我们把中位数理解为合并数组的 (第 (m+n)/2 + 第 (m+n)/2 + 1 ) / 2;

        (m+n)/2 可以写成(m + n + 1)/2

因此我们可以把解题思路变为找到对应较小的值后进行计算

即:

    int n = 0,m = 0;double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {n = nums1.size();m = nums2.size();if(n + m % 2 == 0){return  (fun(nums1,nums2,(n + m)/2) +  fun(nums1,nums2,(n + m)/2 + 1) )/ 2;}else{return fun(nums1,nums2,(n + m + 1)/2);}}

函数 fun如下所示

// 返回nums1,nums2合并后的数组中第x小的值  int fun(vector<int>& nums1, vector<int>& nums2, int x)

用begin记录对应的已计算的下标,data记录begin对应的数据,当一个数组被全部去除后时begin无意义data取一个INT_MAX,不再影响后面的计算

fun()函数里的循环要执行x - 1次,故时间复杂度o(m+n)

    int fun(vector<int>& nums1, vector<int>& nums2, int x) {int begin1 = 0, begin2 = 0;int data1 = n == 0 ? INT_MAX : nums1[begin1];int data2 = m == 0 ? INT_MAX : nums2[begin2];while (x != 1) {if (data1 <= data2) {begin1++;data1 = begin1 == n ? INT_MAX : nums1[begin1];} else if (data1 >= data2) {begin2++;data2 = begin2 == m ? INT_MAX : nums2[begin2];}x -= 1;}return min(data1, data2);}

时间复杂度o(m+n)

ps :虽然还没达到题目要求,但是已经打败了95% 的人

没看懂？没关系我来举个例子演示一遍

解法二:二周目

对一周目进行分析,发现时间时间复杂度主要花在线性的去求第 x 小的数,我们可以把这个线性的方法改成指数级的

class Solution {
public:int n = 0, m = 0;double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {n = nums1.size();m = nums2.size();return ((double)fun(nums1, nums2, (n + m + 1) / 2) +fun(nums1, nums2, (n + m + 2) / 2)) /2;}int fun(vector<int>& nums1, vector<int>& nums2, int x) {if(n == 0)  return nums2[x - 1];if(m == 0)  return nums1[x - 1];int begin1 = 0, begin2 = 0;int len = x / 2;int data1 = nums1[0],data2 = nums2[0];while (x != 1) {len = min(x / 2, min(n - begin1, m - begin2));x -= (len);data1 = (begin1 + len - 1) >= n ? INT_MAX : nums1[begin1 + len - 1];data2 = (begin2 + len - 1) >= m ? INT_MAX : nums2[begin2 + len - 1];if (data1 <= data2) {begin1 += (len);if (begin1 == n)return nums2[begin2 + x - 1];data1 = nums1[begin1];} else if (data1 >= data2) {begin2 += (len);if (begin2 == m)return nums1[begin1 + x - 1];data2 = nums2[begin2];}}return min(data1, data2);}
};

时间复杂度o(log(m+n))

解法三:划分数组

思路:由中位数的定义得:比中位数小的值和比中位数大的值数量是相等的,我们令数组1中从0到i下标的值都比中位数小,从i到末尾的值都大于等与中位数,数组2中从0到j下标的值都比中位数小,从j到末尾的值都大于等与中位数,显而易见每一个i都对应唯一一个j,

举个例子

又因为该数组为升序数组,i左侧恒小于等于i右侧,j同理,故只要满足

i左侧小于等于j右侧

j左侧小于等于i右侧

即可

class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {if (nums1.size() > nums2.size()) {return findMedianSortedArrays(nums2, nums1);}int left = 0,right = nums1.size();int m = nums1.size(),n = nums2.size();int rembermin = 0,rembermax = 0;while(left <= right){int i = (left + right) / 2;int j = (m + n + 1)/2 - i;// 记录四个边界值int data1_left = i == 0 ? INT_MIN : nums1[i - 1];int data1_right = i == m ? INT_MAX : nums1[i];int data2_left = j == 0 ? INT_MIN : nums2[j - 1];int data2_right = j == n ? INT_MAX : nums2[j];if(data1_left <= data2_right){left = i + 1;rembermax = min(data1_right,data2_right);rembermin = max(data1_left,data2_left);}else{right = i - 1;}}return (m + n) % 2 == 0 ? (rembermax + rembermin) / 2.0 : rembermin; }
};