LintCode 486:（快手面试真题）合并K个有序数组

当时没撕出来，下来看了一下，要用到最小堆来进行辅助。整体的算法复杂度是
O(Nlogk)，N是所有点的总数，logk是堆内调整的复杂度
代码如下：

public int[] mergekSortedArrays(int[][] arrays) {
    List<Integer> res = new ArrayList<>();
    int high = arrays.length;
    Queue<int[]> queue = new PriorityQueue<>(high, Comparator.comparingInt(o -> o[0]));
    // 一个三维数组，分别记录这个点的值，所在的数组的编号，以及在数组中的位置
    for (int i = 0; i < high; i++) {
        if (arrays[i].length == 0) continue;
        int[] node = new int[3];
        // value
        node[0] = arrays[i][0];
        // arrayIndex 数组的编号
        node[1] = i;
        // index 值的坐标，这里都是从0开始，可以不写
//            node[2] = 0;
        queue.offer(node);
    }

    while (!queue.isEmpty()) {
        int[] cur = queue.poll();
        res.add(cur[0]);
        // 结点到达当前数组的最后一位
        int arrayIndex = cur[1], index = cur[2];
        // 最后一个元素，不再入队 -- 数组长度不一
        if (index == arrays[arrayIndex].length - 1) continue;
        // 不需要再创建一个数组，直接在原来的cur上面进行修改，再入队即可
        // 下一个位置的value
        cur[0] = arrays[arrayIndex][index + 1];
        // 数组index，不变
//            cur[1] = arrayIndex;
        // 向前一位，index+1
        cur[2] = index + 1;
        queue.offer(cur);
    }
    
	// 应对空数组的情况
    return res.isEmpty() ? new int[0] : res.stream().mapToInt(value -> value).toArray();
}

最后

以上就是温柔项链为你收集整理的LintCode 486:（快手面试真题）合并K个有序数组的全部内容，希望文章能够帮你解决LintCode 486:（快手面试真题）合并K个有序数组所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。