贪心---根据身高重建队列 Posted on 2021-08-14 00:00:00 2021-08-14 00:00:00 by Author 摘要 看到这个题，简直一个头两个大，但是慢慢理解了之后，发现这题真的香，哈哈哈哈！！！ 1. # 贪心---根据身高重建队列 1. - 假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。 请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。 - **提示：** - `1 <= people.length <= 2000` - `0 <= hi <= 106` - `0 <= ki < people.length` - 题目数据确保队列可以被重建 2. 示例描述 - 示例一 ```java 输入：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]] 是重新构造后的队列。 ``` - 示例二 ```java 输入：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]] ``` 3. 解题思路 - 其实拿到本题，我也是一头雾水，不知道如何去解决，简直一点思路都没有，然后查看了许多题解，然后发现一个博主的题解很清晰，并且代码很清奇，于是按照他的讲解我自己再次梳理与自己讲解一遍。 - 首先这题出的有点刁钻，要从两个维度去考虑问题，每个人的排序位置是由这个人本来的升高和他前面比他高的人数来确定的。这是我们能够确定的，但是如果我们一开始做题的时候就从这两个维度入手，那么就像我一样卡死在这个地方出不来了。 - 但是如果先考虑一个维度，然后再考虑另一个维度去解决问题，那么这道题就非常简单了。那么先考虑一个维度在考虑另一个维度，会不会导致排序后的结果不对啊！答案是不会的，因为题目提示说了的，所给的测试数据都能使队列重建。那么一个一个维度考虑怎么会把这个问题解决了尼？ - 这里我的理解是，首先我们按照升高从大到小排列，如果身高相等那么按照比此人高的人数(即就是第二维度)从小达到排序。排序好了之后，就会有一个新的排序数组，这个数组的形式就是个子高的人排在前面，个子矮的人排在后面。个子相同的人，按照比此人高的人数从小到大排序。这里第一维度按照升高已经排序好了，那么接下来就处理第二维度了，第二维度就是该位置比他高的人的数量。首先题目明确的是所给的数据都是正确的，之后我们按照二维的维度进行插入数据，进行重组数组，这里的插入就是按照下标k进行插入。对于之前排序好的数组按照第二维度进行下标插入完之后，整个题目就解决了。 - 那么这里解释一下为什么，对于按照第一次排序好的数组，第二次按照第二维度进行插入重组数据就能保证第n个人前面有比他高的k个人尼。这里其实可以这样想，第一次已经对升高进行降序排序，那么之后进行按照下标k(每个人第二维度)插入的时候，前面已经插入的值往后移动，其实也不影响它第二维度，因为后面插入的人身高他矮，那么第二维度只计算比他高的人的数量，这影响不到第二维度的值。所以就能正确解决本题。其实这里自己手动实现一遍是非常关键的。其实我也是手动排序然后再进行手动插入后才逐渐明白的。 - 其实这两个步骤有贪心思想在里面的，在按照身高从大到小排序后：先按身高高的人的第二维度k来插入。插入操作过后此人满足题目要求，这是局部最优解，然后全部人按照这个思想插入完毕之后，全局得到最优解了。 - 下面就是具体实现逻辑和代码，看后就会发现代码很清奇。 4. 代码示例 ```java public int[][] reconstructQueue(int[][] people) { //表达式进行排序 //根据体重由大到小排序 Arrays.sort(people,(p1,p2)->{ //如果体重相等，按照第二维度从小到大排序 return p1[0]==p2[0]?p1[1] - p2[1] : p2[0] - p1[0]; }); //链表集合 LinkedList<int[]> list = new LinkedList<>(); for (int[] person : people) { //根据第二维度进行有选择的插入节点 list.add(person[1], person); } //返回最终结果 return list.toArray(people); } ```
{{ item.content }}
{{ child.content }}