leetcode 406. Queue Reconstruction by Height（python）_王大呀呀

「這是我參與11月更文挑戰的第19天，活動詳情檢視：2021最後一次更文挑戰」

描述

You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). Each people[i] = [h_i, k_i] represents the i_th person of height h_i with exactly k_i other people in front who have a height greater than or equal to h_i.

Reconstruct and return the queue that is represented by the input array people. The returned queue should be formatted as an array queue, where queue[j] = [h_j, k_j] is the attributes of the jth person in the queue (queue[0] is the person at the front of the queue).

Example 1:

Input: people = [[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]]
Explanation:
Person 0 has height 5 with no other people taller or the same height in front.
Person 1 has height 7 with no other people taller or the same height in front.
Person 2 has height 5 with two persons taller or the same height in front, which is person 0 and 1.
Person 3 has height 6 with one person taller or the same height in front, which is person 1.
Person 4 has height 4 with four people taller or the same height in front, which are people 0, 1, 2, and 3.
Person 5 has height 7 with one person taller or the same height in front, which is person 1.
Hence [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] is the reconstructed queue.

Example 2:

Input: people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
Output: [[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

Note:

1 <= people.length <= 2000
0 <= h_i <= 10^6
0 <= k_i < people.length
It is guaranteed that the queue can be reconstructed.

解析

根據題意，給定一組人 people ，這是佇列中某些人的屬性。每個 people[i] = [h_i, k_i] 代表第 i 個身高為 h_i 的人，前面正好有 k_i 其他身高大於或等於 h_i 的人。題目要求重構並返回輸入陣列 people 所代表的佇列。返回的佇列應格式化為新的陣列 queue ，其中 queue[j] = [h_j, k_j] 為佇列中第 j 個人的屬性（ queue[0] 為佇列最前面的人）。

題目很簡單，就是讓我們把 people 中的元素重新排列，滿足每個元素的身高和位置屬性，並將排列後的陣列返回。因為要滿足前面身高大於等於自己的人數要求，所以先將身高 h 降序排列，同時按 k 升序排列，再按照 k 考慮我們插入的位置，如對例子一進行變化：

 [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] --> [[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]

然後定義一個空列表 result ，開始遍歷上述的列表進行插入：

[7,0] 插入到索引為 0 的位置: [[7,0]]
[7,1] 插入到索引為 1 的位置，前面正好有 1 個身高大於等於他的人: [[7,0], [7,1]]
[6,1] 插入到索引為 1 的位置，前面正好有 1 個身高大於等於他的人: [[7, 0], [6, 1], [7, 1]] 
[5,0] 插入到索引為 0 的位置，前面正好有 0 個身高大於等於他的人: [[5, 0], [7, 0], [6, 1], [7, 1]] 
[5,2] 插入到索引為 2 的位置，前面正好有 2 個身高大於等於他的人: [[5, 0], [7, 0], [5, 2], [6, 1], [7, 1]] 
[4,4]插入到索引為 4 的位置，前面正好有 4 個身高大於等於他的人: [[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]]

解答

class Solution(object):
    def reconstructQueue(self, people):
        """
        :type people: List[List[int]]
        :rtype: List[List[int]]
        """
        people.sort(reverse=True)
        result = []
        for h,k in sorted(people, key=lambda x: (-x[0], x[1])):
            result.insert(k, [h,k])
        return result

執行結果

Runtime: 80 ms, faster than 72.31% of Python online submissions for Queue Reconstruction by Height.
Memory Usage: 14.1 MB, less than 45.38% of Python online submissions for Queue Reconstruction by Height.

原題連結：http://leetcode.com/problems/queue-reconstruction-by-height/

您的支援是我最大的動力