406. 根据身高重修队列（中等）

1. 题目描述

题目中转：406. 根据身高重修队列

2.详细题解

    做一道题之前先静心，默念三遍一切反动派都是纸老虎。已知一个队列，队列中每个数据表示一个属性，[hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或即是 hi 的人，该题要求将打乱顺序的队列规复队列顺序。
  对于一个属性[hi,ki]，如果前面的属性身高均大于即是hi，那么属性[hi, ki] 应该在队列的索引为ki，但因前面存在低于该身高的属性，因此现实索引并不为该值。 那该怎样解决上述题目呢？如今题目的关键是前面可能存在低于该升高的属性，如果能解决此题目，那么该题目则迎刃而解非常简单了。
  应当怎样制止上述题目，如果我们始终按照身高由高到底的顺序规复顺序，那么对于当前身高来说，前序的升高均不低于该升高，此时即可按照索引位置插入了，即接纳贪心策略，贪心的先规复当前队列最高身高属性的位置，对于当前[hi,ki]来说，当前已规复队列中的升高均不低于hi，因此ki即为[hi, ki]对于此时队列所在的索引位置。故算法如下步调如下：
   1.按身高降序分列，身高相同的，按属性值升序分列，为什么呢？
   2.按照身高降序的顺序依次放入队列中，对于第i个人，由于其身高小于即是前面0到i-1的人的身高故第i个人插入的位置并不会影响前面人的属性，由于第i个人前面有kj个人，故插入索引kj处。
  3.留意2中临界条件，当第i个人身高与0到i-1的人身高相同时，第i个人的插入位置则会影响前面人的属性，除非第i个人的位置比所有0到i-1人中同他身高相同的人的位置更靠后，这就回答了1中身高相同的，为什么要按照属性升序分列
3.代码实现

3.1 Python

1. class Solution:
2.     def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
3.         people.sort(key=lambda x:(-x[0], x[1]))
4.         ans = [people[0]]
5.         for x1, x2 in people[1:]:
6.             ans.insert(x2, [x1, x2])
7.         return ans

复制代码

3.2 Java

1. class Solution {
2.     public int[][] reconstructQueue(int[][] people) {
3.         // 使用 Comparator 对数组进行排序，按照 x[0] 降序，x[1] 升序
4.         Arrays.sort(people, new Comparator<int[]>() {
5.             public int compare(int[] a, int[] b) {
6.                 if (a[0] == b[0]) {
7.                     return a[1] - b[1];
8.                 }
9.                 return b[0] - a[0];
10.             }
11.         });
13.         // 使用 LinkedList 存储结果
14.         List<int[]> ansList = new LinkedList<>();
15.         for (int[] person : people) {
16.             ansList.add(person[1], person); // 在位置 person[1] 插入 person
17.         }
19.         // 将 LinkedList 转换为二维数组
20.         int[][] ans = new int[people.length][2];
21.         for (int i = 0; i < people.length; i++) {
22.             ans[i] = ansList.get(i);
23.         }
24.         
25.         return ans;
26.     }
27. }

复制代码

  执行用时不必过于纠结，对比可以发现，对于python和java完全相同的编写，java的时间一样平常是优于python的；至于编写的代码的执行用时击败多少对手，执行用时和网络情况、当条件交代码人数等均有关系，可以尝试完全相同的代码多次执行用时也不是完全相同，只要确保自己代码的算法时间复杂度满足相应要求即可，也可以通过点击分布图查看其它coder的code

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。