一、题目描述

假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对 (h, k) 表示，其中 h 是这个人的身高，k 是排在这个人前面且身高大于或等于 h 的人数。 编写一个算法来重建这个队列。

注意：总人数少于1100人。

输入:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
输出:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

二、题解

方法一：对身高排序

错误思想：仅对身高降序排列后，插入对应的位置。

public int[][] reconstructQueue(int[][] people) {
    Arrays.sort(people, (e1, e2) -> e2[0] - e1[0]);
    List<int[]> list = new ArrayList<>();
    for (int[] p : people) {
        list.add(p[1], p);
    }
    return list.toArray(new int[list.size()][2]);
}

[[9,0],[7,0],[1,9],[3,0],[2,7],[5,3],[6,0],[3,4],[6,2],[5,2]]
输出：[[3,0],[6,0],[7,0],[5,2],[3,4],[6,2],[5,3],[2,7],[9,0],[1,9]]
预期：[[3,0],[6,0],[7,0],[5,2],[3,4],[5,3],[6,2],[2,7],[9,0],[1,9]]

例子表明，对同一身高 h 的人，应该按 k 升序排列才符合题目逻辑。因为 k 表示 i 位置有多少人的身高 >= h[i]，所以，我们应该保证身高相同的人的先后顺序。

public int[][] reconstructQueue(int[][] people) {
    Arrays.sort(people, (e1, e2) -> e1[0] == e2[0] ? e1[1]-e2[1] : e2[0]-e1[0]);
    List<int[]> list = new ArrayList<>();
    for (int[] p : people) {
        list.add(p[1], p);
    }
    return list.toArray(new int[list.size()][2]);
}

复杂度分析

• 时间复杂度：$O(nlogn)$
• 空间复杂度：$O(n)$

转载自原文链接, 如需删除请联系管理员。

原文链接：【贪心】B_011 根据身高重建队列（h 降序 k 升序），转载请注明来源！