当前位置：网站首页>leetcode 406. Queue Reconstruction by Height

leetcode 406. Queue Reconstruction by Height

2022-07-31 07:09:00 【okokabcd】

一、题目大意

标签: 贪心

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

假设有打乱顺序的一群人站成一个队列,数组 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
题目数据确保队列可以被重建

二、解题思路

This question needs to be understood first,一个无序数组,数组中每个元素有两个属性,一个表示身高,One indicates that there are several people in front of him that are as tall or higher than him.Now let's sort this array correctly by its properties.
思路：~~创建一个list,Traverse the array sorted by height,Insert the second property as a positionlist中.~~将people数组排序,再通过一个变量cnt与krelationship to move the element forward to the correct position,The way to move is by swapping positions with the previous element each time.

三、解题方法

3.1 Java实现

public class Solution {
    
    public int[][] reconstructQueue(int[][] people) {
    
        // 先对peopleSort by height
        Arrays.sort(people, (a, b) -> a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);
        for (int i = 1; i < people.length; i++) {
    
            int cnt = 0;
            for (int j = 0; j < i; j++) {
    
                if (cnt == people[i][1]) {
    
                    int[] t = people[i];
                    for (int k = i - 1; k >= j; k--) {
    
                        people[k+1]  = people[k];
                    }
                    people[j] = t;
                    break;
                }
                cnt++;
            }
        }
        return people;
    }
}