|
1 2 3 4 5 6 7 8 9 10 11 12 |
假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。 注意： 总人数少于1100人。 示例 输入: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]] 输出: [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]] |
思路：首先，我们把最大的数字按照顺序排好 ，然后再排小的数，就无所谓了，如图：
插入第一个元素后从第二个元素开始：
此时插入发现第二个元素[7,1]刚好放在第二个位置，K的值也符合
然后第三个元素[6,1]:
这个时候我们需要插入元素[6,1]，注意，数组中已经存在的数据是都比要插入的数据大的
H的值都是7，我们要插入的数据是6，也就是说，6插入在任何位置都不影响前边两个数的
位置，因为k的值是前边>=的个数，[6,1]插入在最开始前边两个元素的k值也是满足的条的
也就是说，我们不需要考虑前边的值，值考虑让[6,1]满足条件即可，那我们就把[6,1]放到位置1
依次类推，完成排序
注意：如果插入的数值H相同，可能会导致数字变化么？不会，因为在第一次按照身高排序的时候，如果相同的，越小的值会樾靠前
代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 |
class Solution(object): def reconstructQueue(self, people): """ :type people: List[List[int]] :rtype: List[List[int]] """ new_people = people new_people.sort(key = lambda x : (-x[0], x[1])) result = [] for i in new_people: result.insert(i[1], i) return result |
Latest posts by Zhiming Zhang (see all)
- aws eks node 自动化扩展工具 Karpenter - 8月 10, 2022
- ReplicationController and ReplicaSet in Kubernetes - 12月 20, 2021
- public key fingerprint - 5月 27, 2021