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

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);}
}