LeetCode_排序_中等_406.根据身高重建队列

痛定思痛。 2023-10-06 22:49 32阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。**每个 people\[i\] = \[hi, ki\] 表示第 i 个人的身高为 hi ，前面正好有 ki 个身高大于或等于 hi 的人**。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue\[j\] = \[hj, kj\] 是队列中第 j 个人的属性（queue\[0\] 是排在队列前面的人）。

**示例 1：**

输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
    输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
    解释：
    编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
    编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
    编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
    编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
    编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
    编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
    因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

**示例 2：**  
输入：people = \[\[6,0\],\[5,0\],\[4,0\],\[3,2\],\[2,2\],\[1,4\]\]  
输出：\[\[4,0\],\[5,0\],\[2,2\],\[3,2\],\[1,4\],\[6,0\]\]

**提示：**  
1 <= people.length <= 2000  
0 <= hi <= 106  
0 <= ki < people.length  
题目数据确保队列可以被重建

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/queue-reconstruction-by-height

## 2.思路 ##

（1）排序  
思路参考[本题官方题解][Link 1]。

## 3.代码实现（Java） ##

//思路1————排序
    class Solution {
        
        public int[][] reconstructQueue(int[][] people) {
        
            /*
                重写排序规则: 按照 hi 为第一关键字降序，ki 为第二关键字升序进行排序。原因如下: 
                按照 hi 进行降序排序，对于每个元素，在其之前的元素的个数，就是大于等于他的元素的数量，
                按照 ki 进行升序排序，我们希望 k 大的尽量在后面，以减少插入操作的次数。
            */
            Arrays.sort(people, (person1, person2) -> {
        
                if (person1[0] != person2[0]) {
        
                    return person2[0] - person1[0];
                } else {
        
                    return person1[1] - person2[1];
                }
            });
            List<int[]> res = new ArrayList<>();
            for (int[] person : people) {
        
                // add(int index，E element): 将元素插入到指定位置的动态数组中
                res.add(person[1], person);
            }
            return res.toArray(new int[res.size()][]);
        }
    }

[Link 1]: https://leetcode.cn/problems/queue-reconstruction-by-height/solution/gen-ju-shen-gao-zhong-jian-dui-lie-by-leetcode-sol/