current position:Home>leetcode 406. Queue Reconstruction by Height(python)

leetcode 406. Queue Reconstruction by Height(python)

2022-01-31 21:42:06 Wang Daya

「 This is my participation 11 The fourth of the yuegengwen challenge 19 God , Check out the activity details :2021 One last more challenge

describe

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.
 Copy code 

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]]
 Copy code 

Note:

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

analysis

According to the meaning , Give a group of people people , This is the attribute of some people in the queue . Every people[i] = [hi, ki] On behalf of the i A height of hi People who , There's just ki Others are taller than or equal to hi People who . The title requires reconstruction and return of the input array people The queue represented . The returned queue should be formatted as a new array queue , among queue[j] = [hj, kj] For the... In the queue j Personal attributes ( queue[0] For the first person in the queue ).

The subject is very simple , Let's put people Rearrange the elements in , Meet the height and position attributes of each element , And return the arranged array to . Because we should meet the requirements of the number of people whose height is greater than or equal to our own in front , So first set the height h Descending order , Press at the same time k Ascending order , Again according to k Consider where we insert , For example, change example 1 :

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

Then define an empty list result , Start traversing the above list to insert :

[7,0]  Insert into index as  0  The location of : [[7,0]]
[7,1]  Insert into index as  1  The location of , There's just  1  A man who is taller than or equal to him : [[7,0], [7,1]]
[6,1]  Insert into index as  1  The location of , There's just  1  A man who is taller than or equal to him : [[7, 0], [6, 1], [7, 1]] 
[5,0]  Insert into index as  0  The location of , There's just  0  A man who is taller than or equal to him : [[5, 0], [7, 0], [6, 1], [7, 1]] 
[5,2]  Insert into index as  2  The location of , There's just  2  A man who is taller than or equal to him : [[5, 0], [7, 0], [5, 2], [6, 1], [7, 1]] 
[4,4] Insert into index as  4  The location of , There's just  4  A man who is taller than or equal to him : [[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]]
 Copy code 

answer

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
        	      
		
 Copy code 

Running results

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.
 Copy code 

Original link :leetcode.com/problems/qu…

Your support is my greatest motivation

copyright notice
author[Wang Daya],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201312142047115.html

Random recommended