Leetcode 406. Queue Reconstruction by Height(python)

题目

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Note:
The number of people is less than 1,100.

Example:
Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

解法：sorting+贪心

• 将数组按照h先进性降序排序
• 而后将数组按照排在前面的人的个数按照升序排序
• 按h从高到低开始，依次插入到output数组，每对pair在output数组中的index为排在这个h前面的人的个数
  详细解析请参考leetcode官方solution

class Solution(object):def reconstructQueue(self, people):""":type people: List[List[int]]:rtype: List[List[int]]"""people = sorted(people, key = lambda x:(-x[0],x[1]))ans = []for person in people:ans.insert(person[1],person)return ans

时间复杂度: O(N^2)，排序复杂度为O(NlogN),然后需要执行N次插入操作，每次插入操作的复杂度为O(K), K为当前output数组中存在的元素，所以一共的复杂度应该是O(N*N)
空间复杂度：O(N),output数组所需的空间

二刷

这道题目的关键在于：放置某一个person的时候，1.保证现在答案里面的所有人都比现在这个人相同或者更大（相应的操作是按照高度降序排序），2. 同时保证与这个人高度相同但是k值更小的已经被放过。在前面两个条件同时满足的情况下，当前person的k值就一定是他在答案中的index

class Solution {
    
public:static bool comparer(vector<int>& a, vector<int>& b){
    return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]);}vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
    sort(people.begin(),people.end(),comparer);vector<vector<int>> ans;for(auto& person : people){
    ans.insert(ans.begin()+person[1],person);}return ans;}
};