leetcode-406 根據身高重建隊列

2021-01-14 AI科技時訊

題目

https://leetcode-cn.com/problems/queue-reconstruction-by-height


假設有打亂順序的一群人站成一個隊列。每個人由一個整數對(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]]


思路

首先，大體上按照身高由大到小的順序進行排序，來保證之後插入的時候我們目標數組的每一個元素都大於我們要插入的元素。之後就好辦了，根據前面有幾個比他高的人來判斷我要將新元素插入到哪個位置，比如前面沒有比他高的人自然就插入到最前面的位置，python的insert函數就像量身為其打造一般。


還有一點需要注意，在身高相同的情況下，前方比本身身高高的人數少的要排在前面。假如兩個人為(x, 0), (x, 1)，那麼為了讓後面的人找到比他高的人（也就是（x, 0）），那麼就需要先將（x, 0）插入其中。不是最高身高的情況也是類似的。


於是，我們就需要進行兩次排序，像箱子排序一樣。所幸，python的sort函數是穩定的，於是我們就先將前方人數進行升序排序，再將身高進行降序排序。之後逐一插入就大功告成了


class Solution:    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:                        people.sort(key = lambda x: [-x[0], x[1]])        res = []        for p in people:            res.insert(p[1], p)          return res

相關焦點

  • 文獻回顧 | 前交叉韌帶重建術後10年預後和危險因素:一項MOON縱向前瞻性隊列研究
    Ten-Year Outcomes and Risk Factors After Anterior Cruciate Ligament Reconstruction: A MOON Longitudinal Prospective Cohort Study前交叉韌帶重建術後10年預後和危險因素：一項MOON縱向前瞻性隊列研究
  • 每天一道leetcode56-合併區間
    正當班主任要繼續發話，只聽到角落默默想起來一個聲音:」K2」前言 2018.11.13號打卡明天的題目：https://leetcode-cn.com/problems/minimum-path-sum/descrip題目 每天一道leetcode56
  • LeetCode數組類知識點&題型總結
    讀取可以直接根據索引，插入和刪除則比較耗時，插一個數據需要移動大量元素，在內存中空出一個元素的空間，然後將要增加的元素放在其中，如果想刪除一個元素，同樣需要移動大量元素去掉被移動的元素。所以如果需求是快速訪問數據，很少或者幾乎不插入和刪除元素，數組是一個不錯的選擇。最常見的有一維數組和二維數組，稍微複雜一點的是多維數組和動態數組。
  • LeetCode刷題第三周【數組(簡單)】
    我們可以根據數組中的索引，快速訪問數組中的元素。事實上，這裡的索引其實就是內存地址。其次，作為線性表的實現方式之一，數組中的元素在內存中是 連續 存儲的，且每個元素佔用相同大小的內存。4.1 解題思路圖中是一個F(5)計算的遞歸樹（圖片來自leetcode官方[7]）。
  • 每天一道leetcode234-回文鍊表
    正當班主任要繼續發話，只聽到角落默默想起來一個聲音:」K2」前言 2018.11.6號打卡明天的題目：https://leetcode-cn.com/problems/remove-linked-list-elements/以後明天的題目提取公布一下哈，因為有些朋友想提前做一下~題目 leetcode234-回文鍊表中文連結：https
  • 通關LeetCode刷題完整攻略,省時又高效
    當然了，根據題目要求，我們可能有固定窗口大小的情況，也有窗口的大小變化的情況。藉助於隊列數據結構，從而能保證樹的節點按照他們的層數列印出來。列印完當前層所有元素，才能執行到下一層。所有這種需要遍歷樹且需要一層一層遍歷的問題，都能用這種模式高效解決。這種樹上的BFS模式是通過把根節點加到隊列中，然後不斷遍歷直到隊列為空。每一次循環中，我們都會把隊頭結點拿出來（remove），然後對其進行必要的操作。
  • [LeetCode] 912. Sort an Array 數組排序
    for (int idx = 0; idx < tmp.size(); ++idx) { nums[idx + start] = tmp[idx]; } }};Github 同步地址:https://github.com/grandyang/leetcode
  • LeetCode面試系列 第6天:No.9 - 迴文數
    迴文數https://leetcode-cn.com/problems/palindrome-number/題目描述判斷一個整數是否是迴文數。迴文數是指正序（從左向右）和倒序（從右向左）讀都是一樣的整數。
  • leetcode鍊表之回文鍊表
    序本文主要記錄一下leetcode鍊表之回文鍊表題目
  • [LeetCode] 976. Largest Perimeter Triangle 最大周長的三角形
    if (A[i] < A[i - 1] + A[i - 2]) { return A[i] + A[i - 1] + A[i - 2]; } } return 0; }};Github 同步地址:https://github.com/grandyang/leetcode
  • LeetCode-66.加一(Plus One)
    來源：力扣（LeetCode）連結：https://leetcode-cn.com/problems/plus-oneLink：https://leetcode.com/problems/plus-one/模擬加O(N)加後反轉數組分別放入個位，十位，百位...
  • leetcode刷對了麼
    今天，逆行君就帶你從世界觀和方法論兩方面走進「leetcode」 簡單來說，leetcode是一個美國的在線編程網站，它收集了各大公司的經典算法面試題，用戶可以選擇不同的語言進行代碼的在線編寫、編譯和調試。
  • leetcode之羅馬數字轉整數
    序本文主要記錄一下leetcode之羅馬數字轉整數題目給定一個羅馬數字，將其轉換成整數。
  • LeetCode-38.外觀數列(Count and Say)
    來源：力扣（LeetCode）連結：https://leetcode-cn.com/problems/count-and-say/Link：https://leetcode.com/problems/count-and-say/模擬法第N個數是對第N - 1個數的外觀描述。
  • 回顧性隊列研究
    隊列研究：是將某一特定人群按是否暴露於某可疑因素或暴露程度分為不同的亞組，追蹤觀察兩組或多組成員結局（如疾病）
  • LeetCode-1732.找到最高海拔(Find the Highest Altitude)
    提示：n == gain.length1 <= n <= 100-100 <= gain[i] <= 100來源：力扣（LeetCode）連結：https://leetcode-cn.com/problems/find-the-highest-altitudeLink：
  • [LeetCode] 996. Number of Squareful Arrays 平方數組的個數
    { if (numCnt[y] > 0 ) { helper(y, left - 1, numCnt, numMap, res); } } ++numCnt[x]; }};Github 同步地址:https://github.com/grandyang/leetcode
  • LeetCode-89.格雷編碼(Gray Code)
    來源：力扣（LeetCode）連結：https://leetcode-cn.com/problems/gray-codeLink：https://leetcode.com/problems/gray-code/回溯法也算是暴力解法，每次異或只變化一個bit位的值, 查看是否可行
  • 數據結構與算法:05 Leetcode同步練習(一)
    題目02：刪除排序數組中的重複項題目03：移除元素題目04：最大子序和題目05：盛最多水的容器題目06：搜索旋轉排序數組題目07：數組中的第K個最大元素題目08：除自身以外數組的乘積題目09：尋找兩個有序數組的中位數題目10：缺失的第一個正數題目01：兩數之和https://leetcode-cn.com
  • 身高越矮,餐後血糖越高?
    身高差異確實和餐後血糖有關！之前的研究已經證實，身高與餐後血糖值呈負相關，而非空腹血糖值（FPG）。同樣，身高與GDM的發病風險呈負相關，而有GDM病史的婦女要比健康婦女平均矮1.1cm。婦女身高越高，GDM風險會降低大約66%。