leetcode 406. Queue Reconstruction by Height(python)

語言: CN / TW / HK

「這是我參與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] = [hi, ki] represents the ith person of height hi with exactly ki other people in front who have a height greater than or equal to hi.

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] = [hj, kj] 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 <= hi <= 10^6
  • 0 <= ki < people.length
  • It is guaranteed that the queue can be reconstructed.

解析

根據題意,給定一組人 people ,這是佇列中某些人的屬性。 每個 people[i] = [hi, ki] 代表第 i 個身高為 hi 的人,前面正好有 ki 其他身高大於或等於 hi 的人。題目要求重構並返回輸入陣列 people 所代表的佇列。 返回的佇列應格式化為新的陣列 queue ,其中 queue[j] = [hj, kj] 為佇列中第 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.

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

您的支援是我最大的動力