【面试常考题目】五种方法解决“如何在n个无序数组中找出它的中位数（java）”问题

news/2024/11/16 20:58:48/

1.3 从N个数组中找到中位数，每一个数组可能乱序

在LeetCode上，"寻找多个数组的中位数"这类问题通常是由两个数组合并中位数问题（即LeetCode第4题）的变种或扩展。直接对应于多个数组合并后寻找中位数的题目在LeetCode上并不常见，但是可以通过扩展第4题的解决方案来处理。

处理多个数组合并后寻找中位数的问题，有几种可能的方法：

  1. 合并后排序：将所有数组合并成一个大数组，然后对这个数组进行排序，最后找到中位数。这种方法简单直接，但如果数组总长度非常大时，可能效率不高。

  2. n路归并排序：合并的时候先将各个数组排序，然后采用n路归并的方式不断的将有序值取出(会用到数组指针，每一个元素对应其数组被取出元素的进度)，直至取出到总长度的一半，时间复杂度为(n*logx)+O(TL),其中前者为各个数组的排序的时间复杂度之和（假设最长的数组长度为x），后者为这n个数组的总长度。

  3. （n路归并的优化）优先队列（堆）：使用最小堆（或最大堆）逐个合并数组。每次从堆中取出最小（或最大）元素，直到达到总长度的一半，以此找到中位数。这种方法比直接排序更高效一些。

  4. 基于快速排序的选择方法（效率最快）：基于215. 数组中的第K个最大元素想出来的一种方法，首先需要将n个数组合并，然后对其基于215题进行求解

  5. 分治+二分法：这是参考LeetCode第4题的一种解决方案。LC第四题是从两个有序数组通过二分找到中位数，那么我们可以先将各个子数组排序，通过分治将数组两两合并成两个大数组，然后再调用LC第四题的方法api完成最终的中位数查找。

尽管LeetCode上可能没有直接对应多个数组合并寻找中位数的题目，上述方法提供了一些处理此类问题的思路。在实际编程挑战或面试中，这些方法可能会派上用场。

1.3.1 合并后排序（略）

1.3.2 合并的时候先将各个数组排序，然后采用n路归并的方式不断的将有序值取出(会用到数组指针，每一个元素对应其数组被取出元素的进度)，直至取出到总长度的一半，时间复杂度为(nlogx)+O(n*TL),其中前者为各个数组的排序的时间复杂度之和（假设最长的数组长度为x），后者TL为这n个数组的总长度。

1 详细步骤

您的方法是一个有效的解决方案，它结合了排序和n路归并排序的思想来找到多个数组中的中位数。以下是对您方法的具体分析：

  1. 先排序：首先对每个数组进行排序。这确保了每个数组内部是有序的，是归并过程中的关键前提。

  2. n路归并：利用归并排序的思路，您维护了一个指针数组来追踪每个数组的当前位置。在每一步中，您会从所有数组的当前位置中选出最小的元素，并将相应数组的指针向前移动一位。

  3. 取出到总长度的一半：由于中位数是位于排序后数组的中间位置，您只需要进行归并操作直到达到所有数组元素总数的一半。这样就可以找到中位数，无需完全归并所有数组。

这种方法的优点是，它避免了对整个合并后的数组进行完整排序，从而减少了不必要的计算，特别是在数据量很大时更有效率。另外，这种方法适用于数组初始时无序的情况，使其成为解决此类问题的一个实用方案。

2 代码实现
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;public class Test3 {public static void main(String[] args) {Random random=new Random();List<List<Integer>>list=new ArrayList<>();int n= random.nextInt(5)+1;for (int i = 0; i < n; i++) {int size= random.nextInt(10)+1;List<Integer>tmp=new ArrayList<>();for (int j = 0; j < size; j++) {tmp.add(random.nextInt(100)-50);}list.add(tmp);}for (int i = 0; i < list.size(); i++) {System.out.println("i:"+i+", "+list.get(i).toString());}System.out.println(getMid(list));}static float getMid(List<List<Integer>>list){list.forEach((o)->{Collections.sort(o);});int n= list.size();if(n==0) return 0.0f;int[]ps=new int[n];int tl=0;for (int i = 0; i < n; i++) {tl+=list.get(i).size();}// corner caseif(tl==1)return list.get(0).get(0);int mid=tl/2;int p=0;int preV=Integer.MAX_VALUE,curV=Integer.MAX_VALUE;while(p<mid+1){int minV=Integer.MAX_VALUE,pos=0;//从n个数组中找到最小那一个及其指针for (int i = 0; i < n; i++) {if(ps[i]<list.get(i).size()&&minV>list.get(i).get(ps[i])){minV=list.get(i).get(ps[i]);pos=i;}}ps[pos]++;//更新当前加入数组的值及其前一个有序值preV=curV;curV=minV;p++;}//总长度为偶数时的返回值if(tl%2==1)return preV;return (float) ((preV+curV)/2.0);}
}

1.3.3 优先队列（对1.3.2方法的改进）：使用一个能装n个元素最小堆逐个合并数组。每次从堆中pop取出最小元素，同时会从pop出的元素所属的数组中再取出一个元素使其填满n个，直到达到总长度的一半，以此找到中位数。这种方法比直接排序更高效一些。

1 详细步骤

使用优先队列（堆）来找到多个数组的中位数是一种高效的方法，特别是当处理多个大型数组时。这种方法的关键在于逐步合并这些数组，同时保持总体的运行效率。以下是具体的步骤和解释：

  1. 初始化优先队列：首先，创建一个最小堆（或最大堆，取决于具体实现）。优先队列（堆）将用于存储每个数组中的元素，同时保持它们的排序顺序。

  2. 填充堆：遍历每个数组，将每个数组的第一个元素（假设数组已排序）加入到优先队列中。为了追踪每个元素属于哪个数组以及在其数组中的位置，你可能需要存储额外的信息，比如数组索引和元素索引。

  3. 逐步取出元素：从优先队列中逐个取出元素。由于优先队列是一个最小堆（或最大堆），每次都能够取出当前所有数组中的最小（或最大）元素。

  4. 继续填充堆：每当从优先队列中取出一个元素，就从该元素所属的数组中取出下一个元素（如果存在）并将其加入到优先队列中。这样做可以保持堆中始终有所有数组中当前未处理的最小（或最大）元素。

  5. 找到中位数：重复上述过程，直到从优先队列中取出了总长度一半的元素。此时，取出的最后一个元素（或者最后两个元素的平均值，取决于总长度是奇数还是偶数）就是中位数。

这种方法的时间复杂度主要由优先队列的操作决定，即O(n log k)，其中n是所有数组中总元素的数量，k是数组的数量。这比直接合并所有数组后进行排序的O(n log n)更高效，特别是当k远小于n时。此外，这种方法的空间复杂度为O(k)，因为优先队列中最多同时包含k个元素。

2 代码实现
import java.util.*;public class Test3 {public static void main(String[] args) {Random random=new Random();List<List<Integer>>list=new ArrayList<>();int n= random.nextInt(2)+1;for (int i = 0; i < 2; i++) {int size= random.nextInt(2)+1;List<Integer>tmp=new ArrayList<>();for (int j = 0; j < size; j++) {tmp.add(random.nextInt(100)-50);}list.add(tmp);}for (int i = 0; i < list.size(); i++) {System.out.println("i:"+i+", "+list.get(i).toString());}System.out.println(getMid(list));}static float getMid(List<List<Integer>>list){list.forEach((o)->{Collections.sort(o);});int n= list.size();if(n==0) return 0.0f;int tl=0;for (int i = 0; i < n; i++) {tl+=list.get(i).size();}// corner caseif(tl==1)return list.get(0).get(0);// entry<arr_id,pos>PriorityQueue<Map.Entry<Integer,Integer>>pq=new PriorityQueue<>((o1,o2)->(list.get(o1.getKey()).get(o1.getValue())-list.get(o2.getKey()).get(o2.getValue())));for (int i = 0; i < n; i++) {pq.offer(new AbstractMap.SimpleEntry<>(i,0));}int mid=tl/2;int p=0;int preV=Integer.MAX_VALUE,curV=Integer.MAX_VALUE;while(p<mid+1){//从n个数组中找到最小那一个及其指针Map.Entry<Integer,Integer>e=pq.poll();int arrId=e.getKey();//属于哪一个数组int pos=e.getValue();//进度指针if(pos+1<list.get(arrId).size()){Map.Entry<Integer,Integer>ne=new AbstractMap.SimpleEntry<>(arrId,pos+1);pq.offer(ne);}//更新当前加入数组的值及其前一个有序值preV=curV;curV=list.get(arrId).get(pos);p++;}if(tl%2==1)return curV;//总长度为偶数时的返回值return (float) ((preV+curV)/2.0);}
}
3 时间复杂度：比1.3.2复杂度更低

时间复杂度为(nlogx)+O(log(n)*TL),其中前者为各个数组的排序的时间复杂度之和（假设最长的数组长度为x），TL后者为这n个数组的总长度。

1.3.4 基于快速排序的选择方法

1 思路

参考LC215数组中的第K个最大元素，这个题采用了基于快速排序的选择方法，时间复杂度是O(n)，我们知道对于长度为n的数组，n为奇数时，n中位数即是第（n/2+1）小的元素，n为偶数时，n中位数即是第（n/2）小的元素和第（n/2+1）小的元素元素之和的一半。我们知道无论k是多少，最坏的时间复杂度为O(n)

2 代码

假设所有数组的总长度为X，则其时间和空间复杂度均为O(X)

import java.util.*;public class Test3 {public static void main(String[] args) {Random random=new Random();List<List<Integer>>list=new ArrayList<>();int n= random.nextInt(2)+1;for (int i = 0; i < 4; i++) {int size= random.nextInt(2)+1;List<Integer>tmp=new ArrayList<>();for (int j = 0; j < size; j++) {tmp.add(random.nextInt(100)-50);}list.add(tmp);}for (int i = 0; i < list.size(); i++) {System.out.println("i:"+i+", "+list.get(i).toString());}System.out.println(getMid(list));}static float getMid(List<List<Integer>>list){List<Integer>tmp=new ArrayList<>();int n=list.size();//合并所有无序的数组for (int i = 0; i < n; i++) {tmp.addAll(list.get(i));}int mid=tmp.size()/2;if(tmp.size()%2==1){return findK(tmp,mid,0,tmp.size()-1);}else{return (float) ((findK(tmp,mid-1,0,tmp.size()-1)+findK(tmp,mid,0,tmp.size()-1))/2.0);}}// 参考LC215. 数组中的第K个最大元素的解法static int findK(List<Integer>ls, int k, int l, int r){Random random=new Random();int rp= random.nextInt(r-l+1)+l;swap(ls,r,rp);int base=ls.get(r);int low=l,high=r;for (int i = l; i <= high;) {if(ls.get(i)>base){swap(ls,i,high--);}else if(ls.get(i)<base){swap(ls,i++,low++);}else {i++;}}if(k<low){return findK(ls, k,l,low-1);}else if(k>=low&&k<=high){return ls.get(low);}return findK(ls,k,high+1,r);}static void swap(List<Integer>ls, int i, int j){int t=ls.get(i);ls.set(i,ls.get(j));ls.set(j,t);}
}

http://www.ppmy.cn/news/1263336.html

相关文章

优化瑞芯微rk3566 tf卡速度uhs SDR104

优化瑞芯微rk3566 tf卡速度uhs SDR104

环境 开发板&#xff1a;orangepi3B CPU:rk3566 TF卡速度标识&#xff1a;C10&#xff0c;U3&#xff0c;V30 起因 对于tf卡启动的系统来说&#xff0c;io会成为一个很关键的瓶颈&#xff0c;所以总希望系统能跑得快一点。我手头用的是一张金士顿的高性能tf卡&#xff0c;开…
阅读更多...
Azure Machine Learning - 使用 Azure OpenAI 服务生成文本

Azure Machine Learning - 使用 Azure OpenAI 服务生成文本

使用 Azure OpenAI 服务生成文本 关注TechLead&#xff0c;分享AI全维度知识。作者拥有10年互联网服务架构、AI产品研发经验、团队管理经验&#xff0c;同济本复旦硕&#xff0c;复旦机器人智能实验室成员&#xff0c;阿里云认证的资深架构师&#xff0c;项目管理专业人士&…
阅读更多...
uView框架的安装与Git管理

uView框架的安装与Git管理

参考链接&#xff1a;Http请求 | uView - 多平台快速开发的UI框架 - uni-app UI框架 安装 打开我们项目的cmd进行下载&#xff1a; yarn add uview-ui 首先我们要确定&#xff0c;未下载前的文件目录以及下载后&#xff0c;是多了个文件目录node_modules 下载完成之后我们就…
阅读更多...
麒麟v10 数据盘初始化 gpt分区

麒麟v10 数据盘初始化 gpt分区

麒麟v10 数据盘初始化 gpt分区 1、查看磁盘 lsblk2 、分区 parted2.1、 设置磁盘分区形式2.2、 设置磁盘的计量单位为磁柱2.3、 分区2.4、 查看分区 3、分区格式化4、 挂载磁盘4.1、新建挂载目录4.2、挂载磁盘4.3、查看挂载结果 5、设置开机自动挂载磁盘分区5.1、 查询磁盘分区…
阅读更多...
Java程序设计实验6 | 集合类

Java程序设计实验6 | 集合类

*本文是博主对Java各种实验的再整理与详解&#xff0c;除了代码部分和解析部分&#xff0c;一些题目还增加了拓展部分&#xff08;⭐&#xff09;。拓展部分不是实验报告中原有的内容&#xff0c;而是博主本人自己的补充&#xff0c;以方便大家额外学习、参考。 &#xff08;解…
阅读更多...
Android studio生成二维码

Android studio生成二维码

1.遇到的问题 需要生成一个二维码&#xff0c;可以使用zxing第三方组件&#xff0c;增加依赖。 //生成二维码 implementation com.google.zxing:core:3.4.1 2.代码 展示页面 <ImageViewandroid:id"id/qrCodeImageView"android:layout_width"150dp"an…
阅读更多...
Python并发-线程和进程

Python并发-线程和进程

一、线程和进程对应的问题 **1.进程&#xff1a;**CPU密集型也叫计算密集型&#xff0c;指的是系统的硬盘、内存性能相对CPU要好很多&#xff0c;此时&#xff0c;系统运作大部分的状况是CPU Loading 100%&#xff0c;CPU要读/写I/O(硬盘/内存)&#xff0c;I/O在很短的时间就可…
阅读更多...
HttpComponents: 领域对象的设计

HttpComponents: 领域对象的设计

1. HTTP协议 1.1 HTTP请求 HTTP请求由请求头、请求体两部分组成&#xff0c;请求头又分为请求行(request line)和普通的请求头组成。通过浏览器的开发者工具&#xff0c;我们能查看请求和响应的详情。 下面是一个HTTP请求发送的完整内容。 POST https://track.abc.com/v4/tr…
阅读更多...
最新文章

Copyright @ 2022~2023