如何找出排名前 500 的数?

如何找出排名前 500 的数?

摘要: 如何找出排名前 500 的数?

如何找出排名前 500 的数?

题目描述

有 20 个数组,每个数组有 500 个元素,并且有序排列。如何在这 20*500 个数中找出前 500 的数?

解答思路

对于 TopK 问题,最常用的方法是使用堆排序。对本题而言,假设数组降序排列,可以采用以下方法:

首先建立大顶堆,堆的大小为数组的个数,即为 20,把每个数组最大的值存到堆中。

接着删除堆顶元素,保存到另一个大小为 500 的数组中,然后向大顶堆插入删除的元素所在数组的下一个元素。

重复上面的步骤,直到删除完第 500 个元素,也即找出了最大的前 500 个数。

为了在堆中取出一个数据后,能知道它是从哪个数组中取出的,从而可以从这个数组中取下一个值,可以把数组的指针存放到堆中,对这个指针提供比较大小的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
import lombok.Data;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
* @author https://github.com/yanglbme
*/
@Data
public class DataWithSource implements Comparable<DataWithSource> {
/**
* 数值
*/
private int value;

/**
* 记录数值来源的数组
*/
private int source;

/**
* 记录数值在数组中的索引
*/
private int index;

public DataWithSource(int value, int source, int index) {
this.value = value;
this.source = source;
this.index = index;
}

/**
*
* 由于 PriorityQueue 使用小顶堆来实现,这里通过修改
* 两个整数的比较逻辑来让 PriorityQueue 变成大顶堆
*/
@Override
public int compareTo(DataWithSource o) {
return Integer.compare(o.getValue(), this.value);
}
}

class Test {
public static int[] getTop(int[][] data) {
int rowSize = data.length;
int columnSize = data[0].length;

// 创建一个columnSize大小的数组,存放结果
int[] result = new int[columnSize];

PriorityQueue<DataWithSource> maxHeap = new PriorityQueue<>();
for (int i = 0; i < rowSize; ++i) {
// 将每个数组的最大一个元素放入堆中
DataWithSource d = new DataWithSource(data[i][0], i, 0);
maxHeap.add(d);
}

int num = 0;
while (num < columnSize) {
// 删除堆顶元素
DataWithSource d = maxHeap.poll();
result[num++] = d.getValue();
if (num >= columnSize) {
break;
}

d.setValue(data[d.getSource()][d.getIndex() + 1]);
d.setIndex(d.getIndex() + 1);
maxHeap.add(d);
}
return result;

}

public static void main(String[] args) {
int[][] data = {
{29, 17, 14, 2, 1},
{19, 17, 16, 15, 6},
{30, 25, 20, 14, 5},
};

int[] top = getTop(data);
System.out.println(Arrays.toString(top)); // [30, 29, 25, 20, 19]
}
}

方法总结

求 TopK,不妨考虑一下堆排序?

评论

:D 一言句子获取中...

加载中,最新评论有1分钟缓存...