如何在多个已排序列表中获取合并后总列表的第N项？

核心问题 #

1. 给定10个独立排序完成的列表，要获取合并为总排序列表后的第N项，是否必须对所有列表做整体排序？
2. 当前已有多路合并的代码，是否循环执行到目标索引是最快的实现方案？

过往类似问题背景 #

之前处理过一个类似但场景不同的问题：10个列表的元素范围是接续前一个列表的（比如列表1元素是1-100，列表2是101-200，以此类推），此时可以直接通过索引计算定位元素，无需排序。

遍历所有元素的代码 #

/* code to iterate through all items in order
 * threads refers to one of the lists */

int sizes[] = new int[threads.size()];
for (int i = 0 ; i < threads.size(); i++) {
    sizes[i] = threads.get(i).data2.size();
}
int n = 0;
int thread = 0;
int size = threads.size();
int offset = 0;
long iterationStart = System.nanoTime();
while (thread < size) {

    // System.out.println(String.format("%d %d", thread, offset + threads.get(thread).data.get(n)));
    int current = offset + threads.get(thread).data.get(n);
    n = n + 1;
    if (n == sizes[thread]) {
        offset += sizes[thread];
        thread++;
        n = 0;
    }
}
long iterationEnd = System.nanoTime();
long iterationTime = iterationEnd - iterationStart;

按索引查找元素的代码 #

int lookupKey = 329131;
int current = lookupKey;
int currentThread = 0;
int total = 0;
while (current >= 0 && currentThread <= size - 1) {
    int next = current - sizes[currentThread];

    if (next >= 0) {
        total += sizes[currentThread];
        current -= sizes[currentThread];
        currentThread++;

    } else {
        break;
    }

}
long lookupEnd = System.nanoTime();
long lookupTime = lookupEnd - lookupStart;
System.out.println(String.format("%d %d",
        currentThread,
        total + threads.get(currentThread).data.get(current)));

当前多路合并代码 #

现在针对元素范围可能重叠的独立有序列表，已有如下多路合并代码：

int size1 = threads.size();

int[] positions = new int[size1];
Arrays.fill(positions, 0);
PriorityQueue<Tuple> pq = new PriorityQueue<>(new Comparator<Tuple>() {
    @Override
    public int compare(Tuple o1, Tuple o2) {
        return o1.value.compareTo(o2.value);
    }
});
long startOrderedIteration = System.nanoTime();

for (ShardedTotalRandomOrder thread : threads) {
    for (int i = 0; i < 10; i++) {
//                System.out.println(thread.data2.get(i));
        pq.add(thread.data2.get(i));
    }
}
List<Integer> overall = new ArrayList<>();
while (!pq.isEmpty()) {
    Tuple poll = pq.poll();
    ArrayList<Tuple> data2 = threads.get(poll.thread).data2;
    if (positions[poll.thread] < data2.size()) {
        Tuple nextValue = data2.get(positions[poll.thread]++);
        pq.offer(nextValue);
    }
    overall.add(poll.value);
    // System.out.println(String.format("%d %d", poll.thread, poll.value));
}
System.out.println(overall);
long endOrderedIteration = System.nanoTime();
long orderedIterationTime = endOrderedIteration - startOrderedIteration;

问题解答 #

1. 是否需要整体排序？ #

不需要。整体排序的时间复杂度是O(M log M)（M是所有列表的总元素数），但我们可以利用列表本身有序的特性，用更高效的方法定位第N项，无需生成完整的合并列表。

2. 循环到目标索引是不是最快的方案？ #

这是一种可行方案，但不一定是最快的，分两种情况讨论：

方案A：优先队列循环取N次（你的现有思路）

• 实现逻辑：用大小为K（列表数量，这里是10）的优先队列，每次取出当前最小元素，然后从对应列表补充下一个元素，重复N次即可得到第N项。
• 时间复杂度：O(N log K)
• 适用场景：当N较小的时候（比如N远小于总元素数M），这个方法高效且实现简单。

方案B：二分查找法（更优的大N场景方案）

• 实现逻辑：利用有序列表的特性，通过二分查找确定一个值mid，统计所有列表中小于等于mid的元素总数，根据总数和N的关系调整二分范围，最终找到第N项。
• 时间复杂度：O(log(max_val - min_val) * K)，其中max_val是所有列表的最大元素，min_val是最小元素。
• 适用场景：当N很大（比如接近M）或者总元素数M非常大的时候，这个方法的效率远高于优先队列方案，因为log(max_val - min_val)通常远小于N。

内容的提问来源于stack exchange，提问作者Samuel Squire