做网站的如何开发业务,四川泸州做网站的公司,贵阳网站建设hsyunso,深圳网站开发工资1.3 从N个数组中找到中位数#xff0c;每一个数组可能乱序
在LeetCode上#xff0c;寻找多个数组的中位数这类问题通常是由两个数组合并中位数问题#xff08;即LeetCode第4题#xff09;的变种或扩展。直接对应于多个数组合并后寻找中位数的题目在LeetCode上…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 randomnew Random();ListListIntegerlistnew ArrayList();int n random.nextInt(5)1;for (int i 0; i n; i) {int size random.nextInt(10)1;ListIntegertmpnew 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(ListListIntegerlist){list.forEach((o)-{Collections.sort(o);});int n list.size();if(n0) return 0.0f;int[]psnew int[n];int tl0;for (int i 0; i n; i) {tllist.get(i).size();}// corner caseif(tl1)return list.get(0).get(0);int midtl/2;int p0;int preVInteger.MAX_VALUE,curVInteger.MAX_VALUE;while(pmid1){int minVInteger.MAX_VALUE,pos0;//从n个数组中找到最小那一个及其指针for (int i 0; i n; i) {if(ps[i]list.get(i).size()minVlist.get(i).get(ps[i])){minVlist.get(i).get(ps[i]);posi;}}ps[pos];//更新当前加入数组的值及其前一个有序值preVcurV;curVminV;p;}//总长度为偶数时的返回值if(tl%21)return preV;return (float) ((preVcurV)/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 randomnew Random();ListListIntegerlistnew ArrayList();int n random.nextInt(2)1;for (int i 0; i 2; i) {int size random.nextInt(2)1;ListIntegertmpnew 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(ListListIntegerlist){list.forEach((o)-{Collections.sort(o);});int n list.size();if(n0) return 0.0f;int tl0;for (int i 0; i n; i) {tllist.get(i).size();}// corner caseif(tl1)return list.get(0).get(0);// entryarr_id,posPriorityQueueMap.EntryInteger,Integerpqnew 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 midtl/2;int p0;int preVInteger.MAX_VALUE,curVInteger.MAX_VALUE;while(pmid1){//从n个数组中找到最小那一个及其指针Map.EntryInteger,Integerepq.poll();int arrIde.getKey();//属于哪一个数组int pose.getValue();//进度指针if(pos1list.get(arrId).size()){Map.EntryInteger,Integernenew AbstractMap.SimpleEntry(arrId,pos1);pq.offer(ne);}//更新当前加入数组的值及其前一个有序值preVcurV;curVlist.get(arrId).get(pos);p;}if(tl%21)return curV;//总长度为偶数时的返回值return (float) ((preVcurV)/2.0);}
}
3 时间复杂度比1.3.2复杂度更低
时间复杂度为(nlogx)O(log(n)*TL),其中前者为各个数组的排序的时间复杂度之和假设最长的数组长度为xTL后者为这n个数组的总长度。
1.3.4 基于快速排序的选择方法
1 思路
参考LC215数组中的第K个最大元素这个题采用了基于快速排序的选择方法时间复杂度是O(n)我们知道对于长度为n的数组n为奇数时n中位数即是第n/21小的元素n为偶数时n中位数即是第n/2小的元素和第n/21小的元素元素之和的一半。我们知道无论k是多少最坏的时间复杂度为O(n)
2 代码
假设所有数组的总长度为X则其时间和空间复杂度均为O(X)
import java.util.*;public class Test3 {public static void main(String[] args) {Random randomnew Random();ListListIntegerlistnew ArrayList();int n random.nextInt(2)1;for (int i 0; i 4; i) {int size random.nextInt(2)1;ListIntegertmpnew 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(ListListIntegerlist){ListIntegertmpnew ArrayList();int nlist.size();//合并所有无序的数组for (int i 0; i n; i) {tmp.addAll(list.get(i));}int midtmp.size()/2;if(tmp.size()%21){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(ListIntegerls, int k, int l, int r){Random randomnew Random();int rp random.nextInt(r-l1)l;swap(ls,r,rp);int basels.get(r);int lowl,highr;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(klow){return findK(ls, k,l,low-1);}else if(klowkhigh){return ls.get(low);}return findK(ls,k,high1,r);}static void swap(ListIntegerls, int i, int j){int tls.get(i);ls.set(i,ls.get(j));ls.set(j,t);}
}
