Question
合并M个长度不一的排序列表
给定M个长度不一的排序列表，并有序的输出。
例如，
输入：在代码中定义4个可变长度的排序列表
[10，20，30，40]
[15,25,35]
[27,29,37,48,93]
[32,33]
输出：
10 15 20 25 27 29 30 32 33 35 37 40 48 93 。使用最小堆
Code
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 java.util.*;
//
class Node implements Comparable<Object>
{
private int value;
private int i;
private int index;
//Node类
public Node(int value, int i, int index) {
this.value = value;
this.i = i;
this.index = index;
}
public int getValue() {
return value;
}
public int getListNum() {
return i;
}
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}
public void setValue(int value) {
this.value = value;
}
public int compareTo(Object o) {
Node node = (Node)o;
return value - node.value;
}
};
public class A076
{
//合并方法
public static void printSorted(List<List<Integer>> list)
{
//创建一个空的最小堆
PriorityQueue<Node> pq = new PriorityQueue<Node>();
for (int i = 0; i < list.size(); i++) {
if (list.get(i).size() >= 1) {
pq.add(new Node(list.get(i).get(0), i, 0));
}
}
while (!pq.isEmpty())
{
Node min = pq.poll();
System.out.print(min.getValue() + " ");
if (min.getIndex() + 1 < list.get(min.getListNum()).size())
{
min.setIndex(min.getIndex() + 1);
min.setValue(list.get(min.getListNum()).get(min.getIndex()));
pq.add(min);
}
}
}
public static void main(String[] args)
{
List<List<Integer>> list = Arrays.asList(
Arrays.asList(10, 20, 30, 40),
Arrays.asList(15, 25, 35),
Arrays.asList(27, 29, 37, 48, 93),
Arrays.asList(32, 33)
);
printSorted(list);
}
}
|
近期评论