有20个数组，每个数组有500个元素，升序排列，现在在这20*500个数中找出排名前500的数。求时间复杂度？

　　　　　　注意：调堆的时间复杂度为logN，建堆的时间复杂度是O(N)。

直接暴力求解，将20个数组合并，然后排序，取出500个数
使用归并。对于排好序的序列，我们要注意使用归并。
先将第1个和第2个归并，得到500个数据（注意，我们不是归并得到100个数）。然后再加结果和第3个归并，得到500个数据，再与第4个归并，等等。
网上的方法，就是堆。保持一个20的堆，然后先将每个数组的第1个数入堆。

20个元素的堆一直保持容量为20个，20个数组的最小元素可以将20个数组的第0个元素入堆，最小堆的性质，顶点为最小值。这时候得到了500个结果里的第0个结果。然后再把下一个元素入20个元素的堆，堆插入的时候会保持性质不变，最小元素依然在顶点。再取出20个元素的顶点，得到500个结果里的第1个结果。

假设 [1,3,4,5,6] [2,3,4,5,6] [3,4,5,6,7]
最小的是比较 1 2 3 得到1
第2小的是将刚才的1替换为后面的元素3 再加上刚才的元素2 3，得到2

注意这儿需要保持数来自于哪个数组，以及其在数组里的位置

// 方法3，保持一个最小堆，这个堆存放来自20个数组的最小数
        // 建立堆的时间复杂度为O(20),
        // 每次取出一个数，然后将该数所在的数组的后面一个数入堆
        // 重复上面步骤，取出500个数
        // 注意建堆的时候需要保持 数来自哪个数组，用一个内部类实现
        // 复杂度是 O（20）+500 * log(20)
        Integer[] result3 = new Integer[500];
        MinHeap<DataWithSource> heap = new MinHeap<DataWithSource>();
        for (int i = 0; i < rowSize; i++) {
            // 记录下来源那个数组，以及在数组中的 index
            DataWithSource d = new DataWithSource(data[i][0], i, 0);
            heap.add(d);
        }

        int num = 0;
        while (num < columnSize) {
            // 删除顶点元素
            DataWithSource d = heap.removeTop();
            result3[num++] = d.getValue();

            // 将 value 置为该数原数组里的下一个数
            d.setValue(data[d.getComeFrom()][d.getIndex() + 1]);

            // 将其在数组中的 index +1
            d.setIndex(d.getIndex() + 1);
            heap.add(d);
        }

有20个数组，每个数组有500个元素，升序排列，现在在这20*500个数中找出排名前500的数。求时间复杂度？

相关推荐