根据身高重建队列

Dear 丶 2024-04-03 07:11 54阅读 0赞

### 406. 根据身高重建队列 ###

> 假设有打乱顺序的一群人站成一个队列，数组 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 < = p e o p l e . l e n g t h < = 2000 1 <= people.length <= 2000 1<=people.length<=2000  
 0 < = h i < = 1 0 6 0 <= hi <= 10^6 0<=hi<=106  
 0 < = k i < p e o p l e . l e n g t h 0 <= ki < people.length 0<=ki<people.length  
题目数据确保队列可以被重建

##### 思路： #####

由于身高较高的学生，不受身高较低的学生影响，所以可以先插入身高较高的学生；

1.  按照 hi为第一关键字降序，
2.  再按ki为第二个关键字升序进行排序
3.  最后根据ki依次插入到新的队列

#### 代码（Java）： ####

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Comparator;
    import java.util.List;
    
    public class requeue {
        
    
    	public static void main(String[] args) {
        
    		// TODO 自动生成的方法存根
    		int [][] people = {
        {
        7,0},{
        4,4},{
        7,1},{
        5,0},{
        6,1},{
        5,2}};
    		int [][] p = reconstructQueue(people);
    		for (int[] person :p) {
        
                System.out.print("["+person[0]+","+person[1]+"]");
            }
    	}
    	public static 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()][]);
    
        }
    
    }

来源：[力扣（LeetCode）][LeetCode]

仅供学习参考。

[LeetCode]: https://leetcode.cn/problems/queue-reconstruction-by-height