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

力扣经典二分题:4. 寻找两个正序数组的中位数

题目链接:4. 寻找两个正序数组的中位数 - 力扣(LeetCode)

一、题目分析

  • 这道题目是让我们在 两个正序的数组中寻找中位数
  • 已知两个数组的大小分别是:int m = nums1.size(),n = nums2.size();
  • 中位数性质1:中位数左侧元素 ≤ 中位数 且 中位数右侧元素 ≥ 中位数 (以升序来看)
  • 中位数性质2:对于一个长度为 N 的数组,中位数将数组一分为二,使得左侧与右侧得元素长度差 ≤ 1
  • 当 m + n 为奇数时,我们需要找到合并后数组中第 k + 1 小的元素,其中 k = (m + n) / 2。
  • 当 m + n 为偶数时,我们需要找到合并后数组中第 k 和第 k + 1 小的元素,然后计算它们的平均值,其中 k = (m + n) / 2 - 1(注意这里 k 是基于 0 的索引,所以实际要找的元素位置是 k 和 k + 1)。

二、算法原理讲解

解法一:暴力排序

通过合并排序的原理,通过中位数的性质,可快速得到中位数的下标,较为简单

时间复杂度为O(M+N),空间复杂度为O(M+N)

解法二:双指针 

时间复杂度为O(M+N),空间复杂度为O(1)

解法三:暴力枚举
解法四:二分优化 
 

三、编写代码

class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int m = nums1.size(), n = nums2.size();if(m > n) swap(nums1,nums2); // 保证nums1始终是较短数组int k = (m + n + 1) / 2; // 应划分给小数组的个数// 枚举 i [0,m]for(int i = 0;i <= m;i++){int&& j = k - i;// 分割线周围的四个值int a = i == m ? INT_MAX :nums1[i];int b = i == 0 ? INT_MIN :nums1[i-1];cout << i << ' ' << j << endl;int c = j == n ? INT_MAX :nums2[j];int d = j == 0 ? INT_MIN :nums2[j-1];// 分割线是否合法if(b <= c && d <= a){if((m + n) % 2 == 1) return max(b,d);else return (double)(max(b,d) + min(c,a)) / 2;}}return 1314.521;}
};

 

class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {// 保证nums1始终是较短数组if(nums1.size() > nums2.size()) swap(nums1,nums2);// 应划分给小数组的个数int k = (nums1.size() + nums2.size() + 1) / 2; // 枚举nums1数组中应该划分给小数组的元素个数(二分优化)int left = 0,right = nums1.size();while(left < right){// mid ∈ [0,m]int i = (left + right + 1) / 2; int j = k - i;cout << i << endl;if(nums1[i-1] <= nums2[j]) left = i;else right = i - 1;}// 分割线两边的值int a = left == nums1.size() ? INT_MAX :nums1[left];int b = left == 0 ? INT_MIN :nums1[left-1];int c = (k-left) == nums2.size() ? INT_MAX :nums2[k-left];int d = (k-left) == 0 ? INT_MIN :nums2[k-left-1];// 处理数据+返回if((nums1.size() + nums2.size()) % 2 == 1) return max(b,d);else return (double)(max(b,d) + min(c,a)) / 2;}
};

http://www.lryc.cn/news/518992.html

相关文章:

  • 解决WordPress出现Fatal error: Uncaught TypeError: ftp_nlist()致命问题
  • Excel 技巧07 - 如何计算到两个日期之间的工作日数?(★)如何排除节假日计算两个日期之间的工作日数?
  • 快速实现一个快递物流管理系统:实时更新与状态追踪
  • kvm 解决 安装windows 虚拟机cpu 核数问题
  • Ansys Fluent Aeroacoustics 应用
  • 119.使用AI Agent解决问题:Jenkins build Pipeline时,提示npm ERR! errno FETCH_ERROR
  • istio-proxy内存指标
  • List详解 - 双向链表的操作
  • 多目标优化算法之一:基于分解的方法
  • conntrack iptables 安全组
  • stringRedisTemplate.execute执行lua脚本
  • HDFS异构存储和存储策略
  • 生成idea ui风格界面代码
  • 嵌入式C语言:二维数组
  • 【机器学习:四、多输入变量的回归问题】
  • JVM实战—OOM的定位和解决
  • iOS 本地新项目上传git仓库,并使用sourceTree管理
  • mysql之基本select语句 运算符 排序分页
  • 如何在 Ubuntu 22.04 上安装 Nagios 服务器教程
  • 数据库事务:确保数据一致性的关键机制
  • 词作词汇积累:错付、大而无当、语焉不详、愈演愈烈
  • selenium学习笔记
  • asp.net core webapi 并发请求时 怎么保证实时获取的用户信息是此次请求的?
  • 实时数仓:基于数据湖的实时数仓与数据治理架构
  • STM32 拓展 RTC案例1:使用闹钟唤醒待机模式 (HAL库)
  • ESP32S3使用串口0作为LOG输出
  • Linux:深入了解fd文件描述符
  • springboot 集成 etcd
  • 03_Redis基本操作
  • pycharm-pyspark 环境安装