滴滴面试题-合并 k 个排序数组

Categories:

题目描述
思路分析
1. 解法一：最小堆多路归并（推荐）
2. 解法二：分治两两合并
相似题目

题目描述

✅ 滴滴面试题-合并 k 个排序数组

给定 N 个有序数组，每个数组的长度为 M，要求将这 N 个有序数组合并成一个有序数组。

思路分析

解法一：最小堆多路归并（推荐）

核心思路：

每个数组当前指针作为堆节点，堆顶始终是最小元素。

弹出堆顶后，将其所在数组的下一个元素入堆。

重复直到堆为空。

复杂度分析：

时间复杂度：O(N log k)，其中 N 为总元素数，k 为数组个数。

空间复杂度：O(k)，堆大小最多为 k。

class Solution {
    public int[] mergeKArrays(int[][] arrays) {
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));
        int total = 0;

        for (int i = 0; i < arrays.length; i++) {
            if (arrays[i].length > 0) {
                pq.offer(new Node(i, 0, arrays[i][0]));
                total += arrays[i].length;
            }
        }

        int[] res = new int[total];
        int idx = 0;

        while (!pq.isEmpty()) {
            Node cur = pq.poll();
            res[idx++] = cur.val;

            int ni = cur.arrayIdx;
            int nj = cur.elemIdx + 1;
            if (nj < arrays[ni].length) {
                pq.offer(new Node(ni, nj, arrays[ni][nj]));
            }
        }

        return res;
    }

    static class Node {
        int arrayIdx;
        int elemIdx;
        int val;

        Node(int arrayIdx, int elemIdx, int val) {
            this.arrayIdx = arrayIdx;
            this.elemIdx = elemIdx;
            this.val = val;
        }
    }
}

import "container/heap"

func mergeKArrays(arrays [][]int) []int {
	total := 0
	h := &minHeap{}

	for i := 0; i < len(arrays); i++ {
		if len(arrays[i]) > 0 {
			heap.Push(h, node{arrayIdx: i, elemIdx: 0, val: arrays[i][0]})
			total += len(arrays[i])
		}
	}

	res := make([]int, 0, total)
	for h.Len() > 0 {
		cur := heap.Pop(h).(node)
		res = append(res, cur.val)

		nj := cur.elemIdx + 1
		if nj < len(arrays[cur.arrayIdx]) {
			heap.Push(h, node{arrayIdx: cur.arrayIdx, elemIdx: nj, val: arrays[cur.arrayIdx][nj]})
		}
	}

	return res
}

type node struct {
	arrayIdx int
	elemIdx  int
	val      int
}

type minHeap []node

func (h minHeap) Len() int           { return len(h) }
func (h minHeap) Less(i, j int) bool { return h[i].val < h[j].val }
func (h minHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *minHeap) Push(x any) {
	*h = append(*h, x.(node))
}

func (h *minHeap) Pop() any {
	old := *h
	n := len(old)
	val := old[n-1]
	*h = old[:n-1]
	return val
}

解法二：分治两两合并

核心思路：

递归将数组集合一分为二，分别合并得到有序数组。

再对两个有序数组进行线性归并。

时间复杂度保持在 O(N log k)。

复杂度分析：

时间复杂度：O(N log k)，其中 N 为总元素数，k 为数组个数。

空间复杂度：O(N)，合并时的临时数组。

class Solution {
    public int[] mergeKArrays(int[][] arrays) {
        if (arrays.length == 0) {
            return new int[0];
        }
        return mergeRange(arrays, 0, arrays.length - 1);
    }

    private int[] mergeRange(int[][] arrays, int left, int right) {
        if (left == right) {
            return arrays[left];
        }

        int mid = left + (right - left) / 2;
        int[] a = mergeRange(arrays, left, mid);
        int[] b = mergeRange(arrays, mid + 1, right);

        return mergeTwo(a, b);
    }

    private int[] mergeTwo(int[] a, int[] b) {
        int[] res = new int[a.length + b.length];
        int i = 0;
        int j = 0;
        int k = 0;

        while (i < a.length && j < b.length) {
            if (a[i] <= b[j]) {
                res[k++] = a[i++];
            } else {
                res[k++] = b[j++];
            }
        }

        while (i < a.length) {
            res[k++] = a[i++];
        }

        while (j < b.length) {
            res[k++] = b[j++];
        }

        return res;
    }
}

func mergeKArrays(arrays [][]int) []int {
	if len(arrays) == 0 {
		return []int{}
	}
	return mergeRange(arrays, 0, len(arrays)-1)
}

func mergeRange(arrays [][]int, left int, right int) []int {
	if left == right {
		return arrays[left]
	}

	mid := left + (right-left)/2
	leftArr := mergeRange(arrays, left, mid)
	rightArr := mergeRange(arrays, mid+1, right)

	return mergeTwo(leftArr, rightArr)
}

func mergeTwo(a []int, b []int) []int {
	res := make([]int, 0, len(a)+len(b))
	i, j := 0, 0

	for i < len(a) && j < len(b) {
		if a[i] <= b[j] {
			res = append(res, a[i])
			i++
		} else {
			res = append(res, b[j])
			j++
		}
	}

	for i < len(a) {
		res = append(res, a[i])
		i++
	}

	for j < len(b) {
		res = append(res, b[j])
		j++
	}

	return res
}

相似题目

题目	难度	考察点
23. 合并 K 个升序链表	困难	堆/分治
373. 查找和最小的 K 对数字	中等	堆
378. 有序矩阵中第 K 小的元素	中等	堆
88. 合并两个有序数组	简单	双指针
632. 最小区间	困难	堆

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/77650347