首页 > 试题广场 > 有20个数组,每个数组有500个元素,并且是有序排列好的,现
[问答题]
20 个数组,每个数组有500 个元素,并且是有序排列好的,现在在这20*500 个数中找出排名前500 的数。
本题原型为:有N个长度不一样的数组,所有数组中的元素都是从小到大有序排列的,请从大到小打印这N个数组整体的前K个数。
我的方法:
1,时间复杂度为O(K*logN);
2,如果所有数组的元素个数M,小于K。则只从大到小打印M个数;

代码实现连带测试用例:

package Test;


import java.util.Arrays;


public class PrintMaxTopKInMatrix {


publicstaticclass HeapNode {

publicint value ;

publicint arrNum ;

publicint index ;


public HeapNode(int value, int arrNum, int index) {

this.value = value;

this.arrNum = arrNum;

this.index = index;

}

}


public static void printTopK(int[][] matrix, int topK) {

int heapSize = matrix.length;

HeapNode[] heap = new HeapNode[heapSize];

for (int i = 0; i != heapSize; i++) {

int index = matrix[i].length - 1;

heap[i] = new HeapNode(matrix[i][index], i, index);

heapInsert(heap, i);

}

System.out.println("TOP " + topK + " : ");

for (int i = 0; i != topK; i++) {

if (heapSize == 0) {

break;

}

System.out.print(heap[0].value + " ");

if (heap[0].index != 0) {

heap[0].value = matrix[heap[0].arrNum][--heap[0].index];

} else {

swap(heap, 0, --heapSize);

}

heapify(heap, 0, heapSize);

}

}


public static void heapInsert(HeapNode[] heap, int index) {

while (index != 0) {

int parent = (index - 1) / 2;

if (heap[parent].value < heap[index].value) {

swap(heap, parent, index);

index = parent;

} else {

break;

}

}

}


public static void heapify(HeapNode[] heap, int index, int heapSize) {

int left = index * 2 + 1;

int right = index * 2 + 2;

int largest = index;

while (left < heapSize) {

if (heap[left].value > heap[index].value) {

largest = left;

}

if (right < heapSize && heap[right].value > heap[largest].value) {

largest = right;

}

if (largest != index) {

swap(heap, largest, index);

} else {

break;

}

index = largest;

left = index * 2 + 1;

right = index * 2 + 2;

}

}


public static void swap(HeapNode[] heap, int index1, int index2) {

HeapNode tmp = heap[index1];

heap[index1] = heap[index2];

heap[index2] = tmp;

}


public static int[][] generateRandomMatrix(int maxRow, int maxCol,

int maxValue) {

if (maxRow < 0 || maxCol < 0) {

returnnull;

}

int[][] matrix = new int[(int) (Math.random() * maxRow) + 1][];

for (int i = 0; i != matrix.length; i++) {

matrix[i] = new int[(int) (Math.random() * maxCol) + 1];

for (int j = 0; j != matrix[i].length; j++) {

matrix[i][j] = (int) (Math.random() * maxValue);

}

Arrays.sort(matrix[i]);

}

return matrix;

}


public static void printMatrix(int[][] matrix) {

for (int i = 0; i != matrix.length; i++) {

for (int j = 0; j != matrix[i].length; j++) {

System.out.print(matrix[i][j] + " ");

}

System.out.println();

}

}


public static void main(String[] args) {

int[][] matrix = generateRandomMatrix(5, 10, 1000);

printMatrix(matrix);

System. out .println("===========================");

printTopK(matrix, 100);

}


}


发表于 2014-11-26 15:04:03 回复(4)
更多回答
推荐
TOP-K问题,用个数为K的最小堆归并处理
发表于 2014-10-25 00:25:59 回复(0)
我觉得的题干中是排列好的序列,然后找20*500中的前500,用多路归并排序中败者树比较好,如果是无序的20*500,用大根堆或者小根堆比较好~~

编辑于 2015-09-02 23:10:13 回复(0)
数组是有序的(假设是升序),我们要利用这个特性。首先构造一个大根堆(大小为数组个数即20),将每个数组当前最大的数放入堆中,然后取出大根堆的根,使用一个统计数组(大小为每个数组的长度即500)保存这个数,将这个数从大根堆中删除,接着再向大根堆中放入刚才删除的那个数的上一个数(数组是有序的),如此反复直到统计数组满了为止。
发表于 2014-11-26 11:37:05 回复(0)
可以先选出20个数组中最大的数,进行比较,选出其中最大的数,然后再从选出最大的那个数组中选出数放入20个数中比较,每次都重复步骤,直到最终选出500个数。20个数的比较可以用堆
发表于 2017-04-27 17:01:30 回复(0)
<div> 两两合并只取前500,再两两合并只取前500 </div> <div> 比较次数应该是19*500 </div>
发表于 2015-09-09 16:04:26 回复(0)
a[20][500]是已有的20个数组
int[] count = new int[20]{0,0,0,0,...0};
int[] result = new int[500];  //result
for(int i=0;i<500;i++){
    int maxValue=0; //最大值
      maxValue=a[0][count[0]];
    for(int j=0;j<20;j++){
       if(maxValue<a[j][count[j]]){
            maxValue=a[j][count[j]];
            count[j]++;
        }
    }
    result [i]=maxValue
}
发表于 2014-11-20 11:28:44 回复(0)
这是一个TOP-N问题,用个数为N的最小堆来解决。
首先读入第一数组的500个数来创建大小为500的小顶堆,建堆的时间复杂度为O(mlogm)(m为数组的大小即为500 ),然后遍历后续19个数组,并与堆顶(最小)元素进行比较。如果比最小的数小,则继续读取后续数字;如果比堆顶的数字大,则替换堆顶元素并重新调整堆为小顶堆。整个过程直至20个数组全部遍历完一遍为止。然后按照中序遍历的方式输出当前堆中的所有500个数字。
发表于 2015-03-29 23:11:11 回复(0)
topk问题,主要在于确定k是多少,k是由所给条件确定。需要根据具体条件确定
发表于 2017-07-30 18:12:04 回复(0)
做一个归并排序

发表于 2015-06-25 19:16:19 回复(0)
mqh头像 mqh
用归并排序
发表于 2014-12-26 08:59:07 回复(0)
用归并的方法,先两两求前500,再两两归并求前500,一直到只剩下最后一条,即前500.
发表于 2014-12-20 11:25:05 回复(0)

发表于 2014-12-20 11:22:23 回复(0)
TOP-K问题,用个数为K的最小堆来解决
发表于 2014-12-11 09:54:06 回复(0)
流头像
桶排序,或用20个节点的最大堆来操作。
发表于 2014-12-10 16:57:50 回复(0)
流头像
桶排序,或用20个节点的最大堆来操作。
发表于 2014-12-10 16:48:41 回复(0)
500*log2(20)
发表于 2014-12-08 18:57:35 回复(0)
使用者10000个数建立大堆排序,取出堆顶元素,保存,相应数据取下一个添加到推中,循环500次
发表于 2014-12-07 10:31:32 回复(0)
1.将5个数组的大小都扩充到100个即 a[0]-a[99],如果顺序是从大到小排列的,那么放置在a[50]-a[99]处,如果是升序,则放在a[0]-a[49]处,其他位置为特殊数字比如0(如果这些数里面包含0就取负数或者什么的)
2.假如是升序排列的,分别取每个数组第49个数比较最大,最大的那个数所在的数组所有元素右移动一个位置。
3.重复步骤2 495次,则每个数组中下标大于等于49的数正好有500个,且是所有数中最大的500个
发表于 2014-12-03 22:37:57 回复(0)
多路归并排序
发表于 2014-12-01 19:57:59 回复(0)
xxj头像 xxj
次问题为top-k问题:
假设20个数组按从大到小排列顺序
解决方法如下
分配一个长度为500的数组A:A[500]
20个指针:分别指向这20数组地址头部
p[0]... ...p[19]
一个循环遍历500次
为代码如下:
for(int i=0;i<500;i++)
{
    temp & *p = GetMaxPointEqual();//找到p[0]...p[19]中最大的元素(最大的有多个取其中一个)返回p[n]
    A[i] = *P;//将这个最大值赋给A[i],找到了第i大的
    P=P->next;//将此p指向下一个比他小的元素
}

发表于 2014-11-28 10:12:00 回复(0)