【面试常考题目】五种方法解决“如何在n个无序数组中找出它的中位数（java）”问题
1.3 从N个数组中找到中位数，每一个数组可能乱序
在LeetCode上，"寻找多个数组的中位数"这类问题通常是由两个数组合并中位数问题（即LeetCode第4题）的变种或扩展。直接对应于多个数组合并后寻找中位数的题目在LeetCode上并不常见，但是可以通过扩展第4题的解决方案来处理。
处理多个数组合并后寻找中位数的问题，有几种可能的方法：
-
合并后排序：将所有数组合并成一个大数组，然后对这个数组进行排序，最后找到中位数。这种方法简单直接，但如果数组总长度非常大时，可能效率不高。
-
n路归并排序：合并的时候先将各个数组排序，然后采用n路归并的方式不断的将有序值取出(会用到数组指针，每一个元素对应其数组被取出元素的进度)，直至取出到总长度的一半，时间复杂度为(n*logx)+O(TL),其中前者为各个数组的排序的时间复杂度之和（假设最长的数组长度为x），后者为这n个数组的总长度。
-
（n路归并的优化）优先队列（堆）：使用最小堆（或最大堆）逐个合并数组。每次从堆中取出最小（或最大）元素，直到达到总长度的一半，以此找到中位数。这种方法比直接排序更高效一些。
-
基于快速排序的选择方法（效率最快）：基于215. 数组中的第K个最大元素想出来的一种方法，首先需要将n个数组合并，然后对其基于215题进行求解
-
分治+二分法：这是参考LeetCode第4题的一种解决方案。LC第四题是从两个有序数组通过二分找到中位数，那么我们可以先将各个子数组排序，通过分治将数组两两合并成两个大数组，然后再调用LC第四题的方法api完成最终的中位数查找。
尽管LeetCode上可能没有直接对应多个数组合并寻找中位数的题目，上述方法提供了一些处理此类问题的思路。在实际编程挑战或面试中，这些方法可能会派上用场。
1.3.1 合并后排序（略）
1.3.2 合并的时候先将各个数组排序，然后采用n路归并的方式不断的将有序值取出(会用到数组指针，每一个元素对应其数组被取出元素的进度)，直至取出到总长度的一半，时间复杂度为(nlogx)+O(n*TL),其中前者为各个数组的排序的时间复杂度之和（假设最长的数组长度为x），后者TL为这n个数组的总长度。
1 详细步骤
您的方法是一个有效的解决方案，它结合了排序和n路归并排序的思想来找到多个数组中的中位数。以下是对您方法的具体分析：
-
先排序：首先对每个数组进行排序。这确保了每个数组内部是有序的，是归并过程中的关键前提。
-
n路归并：利用归并排序的思路，您维护了一个指针数组来追踪每个数组的当前位置。在每一步中，您会从所有数组的当前位置中选出最小的元素，并将相应数组的指针向前移动一位。
-
取出到总长度的一半：由于中位数是位于排序后数组的中间位置，您只需要进行归并操作直到达到所有数组元素总数的一半。这样就可以找到中位数，无需完全归并所有数组。
这种方法的优点是，它避免了对整个合并后的数组进行完整排序，从而减少了不必要的计算，特别是在数据量很大时更有效率。另外，这种方法适用于数组初始时无序的情况，使其成为解决此类问题的一个实用方案。
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 case
if(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 详细步骤
使用优先队列（堆）来找到多个数组的中位数是一种高效的方法，特别是当处理多个大型数组时。这种方法的关键在于逐步合并这些数组，同时保持总体的运行效率。以下是具体的步骤和解释：
-
初始化优先队列：首先，创建一个最小堆（或最大堆，取决于具体实现）。优先队列（堆）将用于存储每个数组中的元素，同时保持它们的排序顺序。
-
填充堆：遍历每个数组，将每个数组的第一个元素（假设数组已排序）加入到优先队列中。为了追踪每个元素属于哪个数组以及在其数组中的位置，你可能需要存储额外的信息，比如数组索引和元素索引。
-
逐步取出元素：从优先队列中逐个取出元素。由于优先队列是一个最小堆（或最大堆），每次都能够取出当前所有数组中的最小（或最大）元素。
-
继续填充堆：每当从优先队列中取出一个元素，就从该元素所属的数组中取出下一个元素（如果存在）并将其加入到优先队列中。这样做可以保持堆中始终有所有数组中当前未处理的最小（或最大）元素。
-
找到中位数：重复上述过程，直到从优先队列中取出了总长度一半的元素。此时，取出的最后一个元素（或者最后两个元素的平均值，取决于总长度是奇数还是偶数）就是中位数。
这种方法的时间复杂度主要由优先队列的操作决定，即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 case
if(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);
}
}
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！