Leetcode日记–406. Queue reconstruction by height

发布于 2020-11-16  121 次阅读


题目如下:

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Note:
The number of people is less than 1,100.

 
Example

Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

思路:

本题即给定了每个人的身高,并告诉我们这个身高的人前面有多少个比他高的人,基于此进行排序。

显然,对于高的人来说,矮的人不算是人(泪目)。换句话说,把矮的人插入到高的人前后并不会影响高的人前面比他高的人的数量。

因此,我们可以对队列中人的高度进行降序排序,排序完成后,对由高到低的人依次重新生成队列。同时,每一次加入队列的人,身高总是小于或等于之前已经入队的人的身高。因此,若当前入队者前面有i个人比他高,则我们可以将其插入第i个位置即可。

对于具体实现来说,因为重新生成队列时我们需要反复在中间插入节点,因此最好使用链表

这里还有一个实现细节。在排序时,若两个人身高一样,我们应该把要求前方身高高于他的人更多者放到后面。比如说有[5,2]和[5,4]两个人,我们应该把[5,2]排在[5,4]前面。因为题目说了 “greater than or equal to h”,也就是说身高相仿的人也是占了一个位置的。

/**
 * 解题思路:先排序再插入
 * 1.排序规则:按照先H高度降序,K个数升序排序
 * 2.遍历排序后的数组,根据K插入到K的位置上
 *
 * 核心思想:高个子先站好位,矮个子插入到K位置上,前面肯定有K个高个子,矮个子再插到前面也满足K的要求
 *
 * @param people
 * @return
 */
        // [7,0], [7,1], [6,1], [5,0], [5,2], [4,4]
        // 再一个一个插入。
        // [7,0]
        // [7,0], [7,1]
        // [7,0], [6,1], [7,1]
        // [5,0], [7,0], [6,1], [7,1]
        // [5,0], [7,0], [5,2], [6,1], [7,1]
        // [5,0], [7,0], [5,2], [6,1], [4,4], [7,1]

代码如下:



class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people,new Comparator<int[]>(){
            @Override
            public int compare(int[] a1, int[] a2) {
                if(a1[0]!=a2[0]){
                    return a2[0] - a1[0];
                }
                else{
                    // 如果两个人身高一样则按照前面的人数的升序进行排列,否则遍历插入时可能出现问题
                    return a1[1] - a2[1];
                }
            }
        });
        List<int[]> res = new LinkedList<>();
        for (int[] a:
             people) {
            res.add(a[1],a);
        }
        return res.toArray(people);
    }
}


你好哇!欢迎来到雷公马碎碎念的地方:)