寻找两个正序数组的中位数[困难]

news/2024/4/16 14:29:03/文章来源:https://blog.csdn.net/zhengzhaoyang122/article/details/136548388

优质博文IT-BLOG-CN

一、题目

给定两个大小分别为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

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

二、代码

二分查找

给定两个有序数组,要求找到两个有序数组的中位数,最直观的思路有以下两种:
【1】使用归并的方式,合并两个有序数组,得到一个大的有序数组。大的有序数组的中间位置的元素,即为中位数。
【2】不需要合并两个有序数组,只要找到中位数的位置即可。由于两个数组的长度已知,因此中位数对应的两个数组的下标之和也是已知的。维护两个指针,初始时分别指向两个数组的下标0的位置,每次将指向较小值的指针后移一位(如果一个指针已经到达数组末尾,则只需要移动另一个数组的指针),直到到达中位数的位置。

假设两个有序数组的长度分别为mn,上述两种思路的复杂度如何?

第一种思路的时间复杂度是O(m+n),空间复杂度是O(m+n)。第二种思路虽然可以将空间复杂度降到O(1),但是时间复杂度仍是 O(m+n)

如何把时间复杂度降低到O(log⁡(m+n))呢?如果对时间复杂度的要求有log,通常都需要用到二分查找,这道题也可以通过二分查找实现。

根据中位数的定义,当m+n是奇数时,中位数是两个有序数组中的第 (m+n)/2个元素,当m+n是偶数时,中位数是两个有序数组中的第(m+n)/2个元素和第(m+n)/2+1个元素的平均值。因此,这道题可以转化成寻找两个有序数组中的第k小的数,其中k(m+n)/2(m+n)/2+1

假设两个有序数组分别是AB。要找到第k个元素,我们可以比较A[k/2−1]B[k/2−1],其中/表示整数除法。由于A[k/2−1]B[k/2−1]的前面分别有A[0 .. k/2−2]B[0 .. k/2−2],即k/2−1个元素,对于A[k/2−1]B[k/2−1]中的较小值,最多只会有 (k/2−1)+(k/2−1)≤k−2(k/2-1)+(k/2-1)个元素比它小,那么它就不能是第k小的数了。

因此我们可以归纳出三种情况:
【1】如果A[k/2−1]<B[k/2−1],则比A[k/2−1]小的数最多只有A的前k/2−1个数和B的前k/2−1个数,即比A[k/2−1]小的数最多只有k−2个,因此A[k/2−1]不可能是第k个数,A[0]A[k/2−1]也都不可能是第k个数,可以全部排除。
【2】如果A[k/2−1]>B[k/2−1],则可以排除B[0]B[k/2−1]
【3】如果A[k/2−1]=B[k/2−1],则可以归入第一种情况处理。
在这里插入图片描述

比较A[k/2−1]B[k/2−1]之后,可以排除k/2个不可能是第k小的数,查找范围缩小了一半。同时,我们将在排除后的新数组上继续进行二分查找,并且根据我们排除数的个数,减少k的值,这是因为我们排除的数都不大于第k小的数。

有以下三种情况需要特殊处理:
【1】如果A[k/2−1]或者B[k/2−1]越界,那么我们可以选取对应数组中的最后一个元素。在这种情况下,我们必须根据排除数的个数减少k的值,而不能直接将k减去k/2
【2】如果一个数组为空,说明该数组中的所有元素都被排除,我们可以直接返回另一个数组中第k小的元素。
【3】如果k=1,我们只要返回两个数组首元素的最小值即可。

用一个例子说明上述算法。假设两个有序数组如下:

A: 1 3 4 9
B: 1 2 3 4 5 6 7 8 9

两个有序数组的长度分别是49,长度之和是13,中位数是两个有序数组中的第7个元素,因此需要找到第k=7个元素。

比较两个有序数组中下标为k/2−1=2的数,即A[2]B[2],如下面所示:

A: 1 3 4 9B: 1 2 3 4 5 6 7 8 9

由于A[2]>B[2],因此排除B[0]B[2],即数组B的下标偏移offset变为3,同时更新 k的值:k=k−k/2=4

下一步寻找,比较两个有序数组中下标为k/2−1=1的数,即A[1]B[4],如下面所示,其中方括号部分表示已经被排除的数。

A: 1 3 4 9B: [1 2 3] 4 5 6 7 8 9

由于A[1]<B[4],因此排除A[0]A[1],即数组A的下标偏移变为2,同时更新k的值:k=k−k/2=2

下一步寻找,比较两个有序数组中下标为k/2−1=0的数,即比较A[2]B[3],如下面所示,其中方括号部分表示已经被排除的数。

A: [1 3] 4 9B: [1 2 3] 4 5 6 7 8 9

由于A[2]=B[3],根据之前的规则,排除A中的元素,因此排除A[2],即数组A的下标偏移变为 3,同时更新k的值: k=k−k/2=1

由于k的值变成1,因此比较两个有序数组中的未排除下标范围内的第一个数,其中较小的数即为第k个数,由于 A[3]>B[3],因此第k个数是B[3]=4

A: [1 3 4] 9B: [1 2 3] 4 5 6 7 8 9
class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {int length1 = nums1.length, length2 = nums2.length;int totalLength = length1 + length2;if (totalLength % 2 == 1) {int midIndex = totalLength / 2;double median = getKthElement(nums1, nums2, midIndex + 1);return median;} else {int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;double median = (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;return median;}}public int getKthElement(int[] nums1, int[] nums2, int k) {/* 主要思路:要找到第 k (k>1) 小的元素,那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较* 这里的 "/" 表示整除* nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个* nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个* 取 pivot = min(pivot1, pivot2),两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个* 这样 pivot 本身最大也只能是第 k-1 小的元素* 如果 pivot = pivot1,那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除",剩下的作为新的 nums1 数组* 如果 pivot = pivot2,那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除",剩下的作为新的 nums2 数组* 由于我们 "删除" 了一些元素(这些元素都比第 k 小的元素要小),因此需要修改 k 的值,减去删除的数的个数*/int length1 = nums1.length, length2 = nums2.length;int index1 = 0, index2 = 0;int kthElement = 0;while (true) {// 边界情况if (index1 == length1) {return nums2[index2 + k - 1];}if (index2 == length2) {return nums1[index1 + k - 1];}if (k == 1) {return Math.min(nums1[index1], nums2[index2]);}// 正常情况int half = k / 2;int newIndex1 = Math.min(index1 + half, length1) - 1;int newIndex2 = Math.min(index2 + half, length2) - 1;int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];if (pivot1 <= pivot2) {k -= (newIndex1 - index1 + 1);index1 = newIndex1 + 1;} else {k -= (newIndex2 - index2 + 1);index2 = newIndex2 + 1;}}}
}

时间复杂度: O(log⁡(m+n)),其中mn分别是数组nums1nums2的长度。初始时有k=(m+n)/2k=(m+n)/2+1,每一轮循环可以将查找范围减少一半,因此时间复杂度是O(log⁡(m+n))
空间复杂度: O(1)

划分数组

方法一的时间复杂度已经很优秀了,但本题存在时间复杂度更低的一种方法。这里给出推导过程,勇于挑战自己的读者可以进行尝试。

为了使用划分的方法解决这个问题,需要理解「中位数的作用是什么」。在统计中,中位数被用来:将一个集合划分为两个长度相等的子集,其中一个子集中的元素总是大于另一个子集中的元素。

如果理解了中位数的划分作用,就很接近答案了。

首先,在任意位置iA划分成两个部分:

           left_A            |          right_AA[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]

由于A中有m个元素, 所以有m+1种划分的方法(i∈[0,m]i \in [0, m]i∈[0,m])

    len(left_A)=i,len(right_A)=m−i

注意:i=0时,left_A为空集, 而当i=m时, right_A为空集。

采用同样的方式,在任意位置jB划分成两个部分:

           left_B            |          right_BB[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]

left_Aleft_B放入一个集合,并将right_Aright_B放入另一个集合。 再把这两个新的集合分别命名为left_partright_part

          left_part          |         right_partA[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]

AB的总长度是偶数时,如果可以确认:

len(left_part)=len(right_part)
max⁡(left_part)≤min⁡(right_part)

那么,{A,B}中的所有元素已经被划分为相同长度的两个部分,且前一部分中的元素总是小于或等于后一部分中的元素。中位数就是前一部分的最大值和后一部分的最小值的平均值:median=max(left_part)+min(right_part)2

AB的总长度是奇数时,如果可以确认:

len(left_part)=len(right_part)+1
max⁡(left_part)≤min⁡(right_part)

那么,{A,B}中的所有元素已经被划分为两个部分,前一部分比后一部分多一个元素,且前一部分中的元素总是小于或等于后一部分中的元素。中位数就是前一部分的最大值:median=max(left_part)

第一个条件对于总长度是偶数和奇数的情况有所不同,但是可以将两种情况合并。第二个条件对于总长度是偶数和奇数的情况是一样的。

要确保这两个条件,只需要保证:i+j=m−i+n−j(当m+n为偶数)或i+j=m−i+n−j+1(当m+n为奇数)。等号左侧为前一部分的元素个数,等号右侧为后一部分的元素个数。将ij全部移到等号左侧,我们就可以得到i+j=(m+n+1)/2。这里的分数结果只保留整数部分。

0≤i≤m0≤j≤n。如果我们规定A的长度小于等于B的长度,即m≤。这样对于任意的i∈[0,m],都有j=m+n+12−i∈[0,n],那么我们在[0,m]的范围内枚举i并得到j,就不需要额外的性质了。
【1】如果A的长度较大,那么我们只要交换AB即可。
【2】如果m>n,那么得出的j有可能是负数。

B[j−1]≤A[i]以及A[i−1]≤B[j],即前一部分的最大值小于等于后一部分的最小值。

为了简化分析,假设A[i−1],B[j−1],A[i],B[j]总是存在。对于i=0i=mj=0j=n这样的临界条件,我们只需要规定A[−1]=B[−1]=−∞A[m]=B[n]=∞即可。这也是比较直观的:当一个数组不出现在前一部分时,对应的值为负无穷,就不会对前一部分的最大值产生影响;当一个数组不出现在后一部分时,对应的值为正无穷,就不会对后一部分的最小值产生影响。

所以我们需要做的是:[0,m]中找到i,使得:B[j−1]≤A[i]A[i−1]≤B[j],其中j=m+n+12−i

我们证明它等价于:[0,m]中找到最大的i,使得:A[i−1]≤B[j],其中j=m+n+12−i

这是因为:
【1】当i0∼m递增时,A[i−1]递增,B[j]递减,所以一定存在一个最大的i满足A[i−1]≤B[j]
【2】如果i是最大的,那么说明i+1不满足。将i+1带入可以得到A[i]>B[j−1],也就是B[j−1]<A[i],就和我们进行等价变换前i的性质一致了(甚至还要更强)。

因此我们可以对i[0,m]的区间上进行二分搜索,找到最大的满足A[i−1]≤B[j]i值,就得到了划分的方法。此时,划分前一部分元素中的最大值,以及划分后一部分元素中的最小值,才可能作为就是这两个数组的中位数。

class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {if (nums1.length > nums2.length) {return findMedianSortedArrays(nums2, nums1);}int m = nums1.length;int n = nums2.length;int left = 0, right = m;// median1:前一部分的最大值// median2:后一部分的最小值int median1 = 0, median2 = 0;while (left <= right) {// 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]// 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]int i = (left + right) / 2;int j = (m + n + 1) / 2 - i;// nums_im1, nums_i, nums_jm1, nums_j 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]int nums_im1 = (i == 0 ? Integer.MIN_VALUE : nums1[i - 1]);int nums_i = (i == m ? Integer.MAX_VALUE : nums1[i]);int nums_jm1 = (j == 0 ? Integer.MIN_VALUE : nums2[j - 1]);int nums_j = (j == n ? Integer.MAX_VALUE : nums2[j]);if (nums_im1 <= nums_j) {median1 = Math.max(nums_im1, nums_jm1);median2 = Math.min(nums_i, nums_j);left = i + 1;} else {right = i - 1;}}return (m + n) % 2 == 0 ? (median1 + median2) / 2.0 : median1;}
}

时间复杂度: O(log⁡min⁡(m,n))),其中mn分别是数组nums1nums2的长度。查找的区间是[0,m],而该区间的长度在每次循环之后都会减少为原来的一半。所以,只需要执行log⁡m次循环。由于每次循环中的操作次数是常数,所以时间复杂度为O(log⁡m)。由于我们可能需要交换nums1nums2使得m≤n,因此时间复杂度是O(log⁡min⁡(m,n)))

空间复杂度: O(1)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_999061.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

TCP包头、TCP为什么安全可靠、UDP和TCP的区别、http协议

我要成为嵌入式高手之3月8日Linux高编第十八天&#xff01;&#xff01; __________________________________________________ 学习笔记 TPC包头 1、序号 发送端发送数据包的编号 2、确认号 已经确认接收到的数据的编号&#xff0c;只有当ACK为1时&#xff0c;该位才有用 …

打开stable diffusion webui时,提示缺少clip或clip安装不上怎么办

在当前数字化时代&#xff0c;软件工具的应用已经成为人们日常生活和工作中不可或缺的一部分。而在使用各种软件工具的过程中&#xff0c;遇到一些技术性问题也是常有的事情。比如&#xff0c;在打开 Stable Diffusion WebUI 这样一个功能强大的工具时&#xff0c;有时会遇到缺…

Python算法题集_搜索二维矩阵

Python算法题集_搜索二维矩阵 题51&#xff1a;搜索二维矩阵1. 示例说明2. 题目解析- 题意分解- 优化思路- 测量工具 3. 代码展开1) 标准求解【矩阵展开为列表二分法】2) 改进版一【行*列区间二分法】3) 改进版二【第三方模块】 4. 最优算法5. 相关资源 本文为Python算法题集之…

图论入门题题解

✨欢迎来到脑子不好的小菜鸟的文章✨ &#x1f388;创作不易&#xff0c;麻烦点点赞哦&#x1f388; 所属专栏&#xff1a;刷题_脑子不好的小菜鸟的博客-CSDN博客 我的主页&#xff1a;脑子不好的小菜鸟 文章特点&#xff1a;关键点和步骤讲解放在 代码相应位置 拓扑排序 / 家谱…

vscode setting.json 全局设置 工作区设置 位置 优先级

vscode中setting.json有两种配置权限 一、全局配置&#xff1a;setting.json文件位于C:\Users\Administrator\AppData\Roaming\Code\User\settings.json 二、工作区配置&#xff1a;setting.json文件位于工作区的.vscode\settings.json 当两种配置同时存在时&#xff0c;工作区…

<商务世界>《第9课 产品地图》

1 产品地图 产品地图的核心是产品或用户的业务流程或地图导航&#xff0c;从用户和产品两条路线出发&#xff0c;搭建业务架构&#xff0c;并划分明确的功能模块&#xff0c;用图形化方式记录、整理、表现出产品的清晰特点。其中&#xff0c;包括用户在使用过程中做了什么、感…

计算机网络-网络应用服务器

1.网络操作系统&#xff1a; 用统一的方法管理各主机之间的通信和资源的共享。主要功能&#xff1a;网络通信、共享资源、网络管理、网络服务、互操作、网络接口。四大特征&#xff1a;并发、资源共享、虚拟、异步性。安全性&#xff1a;用户账号、时间限制、地点限制、磁盘空间…

【数据结构】单链表的层层实现!! !

关注小庄 顿顿解馋(●’◡’●) 上篇回顾 我们上篇学习了本质为数组的数据结构—顺序表&#xff0c;顺序表支持下标随机访问而且高速缓存命中率高&#xff0c;然而可能造成空间的浪费&#xff0c;同时增加数据时多次移动会造成效率低下&#xff0c;那有什么解决之法呢&#xff…

特种车日常检修VR虚拟互动培训软件节省大量的教学资源和成本

随着科技的不断发展&#xff0c;虚拟现实(VR)技术已经逐渐融入了各行各业&#xff0c;其中特种车辆的养护教学也从中受益匪浅。VR虚拟仿真教学在特种车辆养护领域的应用&#xff0c;不仅创新了教学方式&#xff0c;还为提高学员的学习效果和实际操作技能提供了强有力的支持。 特…

c# combox 行间距调整

初始化combox comboBox1.DropDownStyle ComboBoxStyle.DropDownList;comboBox1.ItemHeight 25; // 设置 combox 的行高comboBox1.DrawMode DrawMode.OwnerDrawVariable; 添加 DrawItem 事件 private void comboBox1_DrawItem(object sender, DrawItemEventArgs e){if (…

ArrayList常用API

常见方法 add 增remove 删set 改get 查clear 清空元素size 长度isEmpty 为空判断 用法 // String就是泛型 这种使用方法对于限制类型很有用 ArrayList<String> arrayList new ArrayList<>();// add 添加元素 返回的是boolean 代表是否添加成功 arrayList.add(&qu…

【Neo4j系列】Neo4j之CQL语句和函数介绍

本文将对Neo4j中的CQL语句和CQL函数进行详细介绍。 作者&#xff1a;后端小肥肠 目录 1. 前言 2. CQL语句 2.1. CQL简介 2.2. CREATE命令 2.3. MATCH命令 2.4. RETURN命令 2.5. MATCH和RETURN 2.6. CREATEMATCHRETURN命令 2.7. 关系基础 2.8. CREATE创建标签 2.9. WH…

Unity 让角色动起来(动画控制器)

下载素材&#xff1a; 导入后&#xff0c;找到预制体和动画。 新建动画控制器&#xff0c;拖动到预制体的新版动画组件上。 建立动画关系 创建脚本&#xff0c;挂载到预制体上。 using System.Collections; using System.Collections.Generic; using UnityEngine;public c…

AIGC启示录:深度解析AIGC技术的现代性与系统性的奇幻旅程

✨✨ 欢迎大家来访Srlua的博文&#xff08;づ&#xffe3;3&#xffe3;&#xff09;づ╭❤&#xff5e;✨✨ &#x1f31f;&#x1f31f; 欢迎各位亲爱的读者&#xff0c;感谢你们抽出宝贵的时间来阅读我的文章。 我是Srlua小谢&#xff0c;在这里我会分享我的知识和经验。&am…

Cloud-Eureka服务治理-Ribbon负载均衡

构建Cloud父工程 父工程只做依赖版本管理 不引入依赖 pom.xml <packaging>pom</packaging><parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</artifactId><version>2.3.9.RELEA…

【C语言】数据类型和变量

前言&#x1f49e;&#x1f49e; 啦啦啦~这里是土土数据结构学习笔记&#x1f973;&#x1f973; &#x1f4a5;个人主页&#xff1a;大耳朵土土垚的博客 &#x1f4a5; 所属专栏&#xff1a;C语言笔记 &#x1f4a5;欢迎大家&#x1f973;&#x1f973;点赞✨收藏&#x1f49…

二维码门楼牌管理系统在教育领域的应用及其优势

文章目录 前言一、二维码门楼牌管理系统概述二、教育领域的应用场景三、二维码门楼牌管理系统的优势四、结语 前言 随着信息技术的快速发展&#xff0c;二维码门楼牌管理系统在教育领域的应用越来越广泛。该系统不仅提高了地址信息的准确性&#xff0c;还为学校、家长和教育工…

分库分表

分库分表 1 分库分表介绍1.1、分库分表概述1.2、分库分表场景示例1.3、大数据存储下数据库性能分析1.4、小结 2 分库分表方式2.1、垂直分表2.2、垂直分库2.3、水平分表2.4、水平分库2.5、分库分表带来的问题2.6、分库分表小结 1 分库分表介绍 1.1、分库分表概述 分库分表本质…

k8s常用命令大全

k8s常用的命令 下面是一些常用的Kubernetes&#xff08;K8s&#xff09;命令&#xff0c;以及它们的简要说明。这些命令可以帮助您管理和操作Kubernetes集群中的资源。 集群管理命令&#xff1a; kubectl cluster-info: 显示集群的基本信息。 kubectl config use-context &l…

QT:用opencv的KNN识别图片中的LED数字(一)

前言 一款功能测试的软件demo,使用了QT作为界面,主要使用了opencv的KNN识别,使用gstreamer作为管道,用来打开图片。后期会写一篇打开摄像头实时识别的文章。 (正在写,未完成,稍候) 效果一预览: 效果二预览: 效果三预览: 正在写。。。 设计思路 1. 软件UI设计 2. …