根据身高重建队列

假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(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]]


2020.11.15 中国人寿研发中心2021秋招题

通过次数60,640提交次数86,098

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/queue-reconstruction-by-height
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目的意思是原来K的顺序不对（也就是原来的顺序不能保证k成立），要用一种规则，使得每个{h,k}所对应的顺序是正常的。例如{5,0}身高大于5的不能站在{5，0}的前面，{7，0}是身高大于7的不允许站在{7，0}前面,{5,2}是只允许2个身高大于等于{5，2}的人站在{5，2}前面。

解题思路：

1. 先按照k从小到大排序一波，保证排在后面的移动少
2. 然后使用表格记录排序后的每个人的前面有几个人比他高或相等
3. 用比他高或相等的人的数量减去正确顺序时前面比他高或相等的人的数量（也就是他的k）得到他应该向前移动的数量
4. 根据他应该移动的数量，对其向前移动，得到的顺序即为正确的顺序

class Solution {
    public int[][] reconstructQueue(int[][] people) {
       Arrays.sort(people, new Comparator<int[]>() {//对k进行排序
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });

        int len = people.length;
        int dp[] = new int[len];//记录每个人前面有几个人的身高大于等于他
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (people[i][0] <= people[j][0]) {
                    dp[i]++;
                }
            }
            //(dp[i] - people[i][1])是当前的人应该向前移动的位置
            list.add(i - (dp[i] - people[i][1]), people[i]);
        }

        for (int i = 0; i < list.size(); i++) {//转换输出
            people[i] = list.get(i);
        }
        return people;
    }
}

官方题解解题思路

同样地，我们也可以将每个人按照身高从大到小进行排序，处理身高相同的人使用的方法类似，即：按照 $h_i$ 为第一关键字降序，$k_i$
​
为第二关键字升序进行排序。如果我们按照排完序后的顺序，依次将每个人放入队列中，那么当我们放入第 $i$个人时：

第 $0$, $\cdots$,$i−1$ 个人已经在队列中被安排了位置，他们只要站在第$i$个人的前面，就会对第$ i$ 个人产生影响，因为他们都比第 $i$ 个人高；

而第 $i+1$, $\cdots$,n−1 个人还没有被放入队列中，并且他们无论站在哪里，对第 $i$ 个人都没有任何影响，因为他们都比第 $i$个人矮。

在这种情况下，我们无从得知应该给后面的人安排多少个「空」位置，因此就不能沿用方法一。但我们可以发现，后面的人既然不会对第 $i$ 个人造成影响，我们可以采用「插空」的方法，依次给每一个人在当前的队列中选择一个插入的位置。也就是说，当我们放入第 $i$ 个人时，只需要将其插入队列中，使得他的前面恰好有 $k_i$ 个人即可。

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator<int[]>() {
            public int compare(int[] person1, int[] person2) {
                if (person1[0] != person2[0]) {
                    return person2[0] - person1[0];
                } else {
                    return person1[1] - person2[1];
                }
            }
        });
        List<int[]> ans = new ArrayList<int[]>();
        for (int[] person : people) {
            ans.add(person[1], person);
        }
        return ans.toArray(new int[ans.size()][]);
    }
}

参考文献

官方题解

赏

谢谢你请我吃糖果

微信