406. 根据身高重修队列（中等）
1. 题目描述题目中转：406. 根据身高重修队列
https://img-blog.csdnimg.cn/direct/cd6a6de3a4ef4d13bc80d25c9a2584b9.png
https://img-blog.csdnimg.cn/direct/f4f41862825a4b549e949ecec215d63d.png
2.详细题解
做一道题之前先静心，默念三遍一切反动派都是纸老虎。已知一个队列，队列中每个数据表示一个属性， 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或即是 hi 的人，该题要求将打乱顺序的队列规复队列顺序。
对于一个属性，如果前面的属性身高均大于即是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
class Solution:
def reconstructQueue(self, people: List]) -> List]:
people.sort(key=lambda x:(-x, x))
ans = ]
for x1, x2 in people:
ans.insert(x2, )
return ans
https://img-blog.csdnimg.cn/direct/a6d0d97ccc3542ed80f74500bc8f8f63.png
3.2 Java
class Solution {
public int[][] reconstructQueue(int[][] people) {
// 使用 Comparator 对数组进行排序，按照 x 降序，x 升序
Arrays.sort(people, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
if (a == b) {
return a - b;
}
return b - a;
}
});
// 使用 LinkedList 存储结果
List<int[]> ansList = new LinkedList<>();
for (int[] person : people) {
ansList.add(person, person); // 在位置 person 插入 person
}
// 将 LinkedList 转换为二维数组
int[][] ans = new int;
for (int i = 0; i < people.length; i++) {
ans = ansList.get(i);
}
return ans;
}
}
https://img-blog.csdnimg.cn/direct/18ffdf2ecd464ca5ad45408e0d954d36.png
执行用时不必过于纠结，对比可以发现，对于python和java完全相同的编写，java的时间一样平常是优于python的；至于编写的代码的执行用时击败多少对手，执行用时和网络情况、当条件交代码人数等均有关系，可以尝试完全相同的代码多次执行用时也不是完全相同，只要确保自己代码的算法时间复杂度满足相应要求即可，也可以通过点击分布图查看其它coder的code
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]