LeetCode : 406. Queue Reconstruction by Height 重构身高，序号队列

亦凉 2021-06-24 16:10 281阅读 0赞

**试题**  
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\]\]  
**代码：**  
按照插入的顺序，首先我们要插入身高高的人以防止后来的插入者影响身高低的人的序号。  
如果已经插入 \[7,0\]，\[7,1\]，这时候如果来了一个身高8的人容易影响身高7的人已存在的排序，但如果来的是小于身高7的人，那么就不会影响。因此我们要将序列按身高降序排列。  
对于同等身高的人来说，我们要优先插入排在前面的人，以确定序号。如 \[7,0\]，\[7,1\]和\[5,0\], \[7,0\], \[5,2\], \[6,1\], \[7,1\]。因此我们要按序号升序排列等高人。

class Solution {
        public int[][] reconstructQueue(int[][] people) {
            if(people==null || people.length==0)
                return new int[0][0];
            
            Arrays.sort(people, (a,b)-> a[0]==b[0]?a[1]-b[1]:b[0]-a[0]);
            
            ArrayList<int[]> out = new ArrayList<>();
            for(int[] p : people){
                out.add(p[1],p);
            }
            return out.toArray(new int[people.length][]);
        }
    }