成人免费xxxxx在线视频软件_久久精品久久久_亚洲国产精品久久久_天天色天天色_亚洲人成一区_欧美一级欧美三级在线观看

如何根據身高重建隊列,你學會了嗎?

網絡 通信技術
假設有打亂順序的一群人站成一個隊列,數組 people 表示隊列中一些人的屬性(不一定按順序)。每個 people[i] = [hi, ki] 表示第 i 個人的身高為 hi ,前面 正好 有 ki 個身高大于或等于 hi 的人。

[[436919]]

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

假設有打亂順序的一群人站成一個隊列,數組 people 表示隊列中一些人的屬性(不一定按順序)。每個 people[i] = [hi, ki] 表示第 i 個人的身高為 hi ,前面 正好 有 ki 個身高大于或等于 hi 的人。

請你重新構造并返回輸入數組 people 所表示的隊列。返回的隊列應該格式化為數組 queue ,其中 queue[j] = [hj, kj] 是隊列中第 j 個人的屬性(queue[0] 是排在隊列前面的人)。

示例 1:

  • 輸入:people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
  • 輸出:[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
  • 解釋:
    • 編號為 0 的人身高為 5 ,沒有身高更高或者相同的人排在他前面。
    • 編號為 1 的人身高為 7 ,沒有身高更高或者相同的人排在他前面。
    • 編號為 2 的人身高為 5 ,有 2 個身高更高或者相同的人排在他前面,即編號為 0 和 1 的人。
    • 編號為 3 的人身高為 6 ,有 1 個身高更高或者相同的人排在他前面,即編號為 1 的人。
    • 編號為 4 的人身高為 4 ,有 4 個身高更高或者相同的人排在他前面,即編號為 0、1、2、3 的人。
    • 編號為 5 的人身高為 7 ,有 1 個身高更高或者相同的人排在他前面,即編號為 1 的人。
    • 因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新構造后的隊列。

示例 2:

  • 輸入:people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
  • 輸出:[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

提示:

  • 1 <= people.length <= 2000
  • 0 <= hi <= 10^6
  • 0 <= ki < people.length

題目數據確保隊列可以被重建

思路

本題有兩個維度,h和k,看到這種題目一定要想如何確定一個維度,然后在按照另一個維度重新排列。

其實如果大家認真做了135. 分發糖果,就會發現和此題有點點的像。

在135. 分發糖果我就強調過一次,遇到兩個維度權衡的時候,一定要先確定一個維度,再確定另一個維度。

如果兩個維度一起考慮一定會顧此失彼。

對于本題相信大家困惑的點是先確定k還是先確定h呢,也就是究竟先按h排序呢,還先按照k排序呢?

如果按照k來從小到大排序,排完之后,會發現k的排列并不符合條件,身高也不符合條件,兩個維度哪一個都沒確定下來。

那么按照身高h來排序呢,身高一定是從大到小排(身高相同的話則k小的站前面),讓高個子在前面。

此時我們可以確定一個維度了,就是身高,前面的節點一定都比本節點高!

那么只需要按照k為下標重新插入隊列就可以了,為什么呢?

以圖中{5,2} 為例:

根據身高重建隊列

按照身高排序之后,優先按身高高的people的k來插入,后序插入節點也不會影響前面已經插入的節點,最終按照k的規則完成了隊列。

所以在按照身高從大到小排序后:

  • 局部最優:優先按身高高的people的k來插入。插入操作過后的people滿足隊列屬性
  • 全局最優:最后都做完插入操作,整個隊列滿足題目隊列屬性

局部最優可推出全局最優,找不出反例,那就試試貪心。

一些同學可能也會疑惑,你怎么知道局部最優就可以推出全局最優呢?有數學證明么?

在貪心系列開篇詞關于貪心算法,你該了解這些!中,我已經講過了這個問題了。

刷題或者面試的時候,手動模擬一下感覺可以局部最優推出整體最優,而且想不到反例,那么就試一試貪心,至于嚴格的數學證明,就不在討論范圍內了。

如果沒有讀過關于貪心算法,你該了解這些!的同學建議讀一下,相信對貪心就有初步的了解了。

回歸本題,整個插入過程如下:

排序完的people:[[7,0], [7,1], [6,1], [5,0], [5,2],[4,4]]

插入的過程:

  • 插入[7,0]:[[7,0]]
  • 插入[7,1]:[[7,0],[7,1]]
  • 插入[6,1]:[[7,0],[6,1],[7,1]]
  • 插入[5,0]:[[5,0],[7,0],[6,1],[7,1]]
  • 插入[5,2]:[[5,0],[7,0],[5,2],[6,1],[7,1]]
  • 插入[4,4]:[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

此時就按照題目的要求完成了重新排列。

C++代碼如下:

  1. // 版本一 
  2. class Solution { 
  3. public
  4.     static bool cmp(const vector<int> a, const vector<int> b) { 
  5.         if (a[0] == b[0]) return a[1] < b[1]; 
  6.         return a[0] > b[0]; 
  7.     } 
  8.     vector<vector<int>> reconstructQueue(vector<vector<int>>& people) { 
  9.         sort (people.begin(), people.end(), cmp); 
  10.         vector<vector<int>> que; 
  11.         for (int i = 0; i < people.size(); i++) { 
  12.             int position = people[i][1]; 
  13.             que.insert(que.begin() + position, people[i]); 
  14.         } 
  15.         return que; 
  16.     } 
  17. }; 
  • 時間復雜度O(nlogn + n^2)
  • 空間復雜度O(n)

但使用vector是非常費時的,C++中vector(可以理解是一個動態數組,底層是普通數組實現的)如果插入元素大于預先普通數組大小,vector底部會有一個擴容的操作,即申請兩倍于原先普通數組的大小,然后把數據拷貝到另一個更大的數組上。

所以使用vector(動態數組)來insert,是費時的,插入再拷貝的話,單純一個插入的操作就是O(n^2)了,甚至可能拷貝好幾次,就不止O(n^2)了。

改成鏈表之后,C++代碼如下:

  1. // 版本二 
  2. class Solution { 
  3. public
  4.     // 身高從大到小排(身高相同k小的站前面) 
  5.     static bool cmp(const vector<int> a, const vector<int> b) { 
  6.         if (a[0] == b[0]) return a[1] < b[1]; 
  7.         return a[0] > b[0]; 
  8.     } 
  9.     vector<vector<int>> reconstructQueue(vector<vector<int>>& people) { 
  10.         sort (people.begin(), people.end(), cmp); 
  11.         list<vector<int>> que; // list底層是鏈表實現,插入效率比vector高的多 
  12.         for (int i = 0; i < people.size(); i++) { 
  13.             int position = people[i][1]; // 插入到下標為position的位置 
  14.             std::list<vector<int>>::iterator it = que.begin(); 
  15.             while (position--) { // 尋找在插入位置 
  16.                 it++; 
  17.             } 
  18.             que.insert(it, people[i]); 
  19.         } 
  20.         return vector<vector<int>>(que.begin(), que.end()); 
  21.     } 
  22. }; 
  • 時間復雜度O(nlogn + n^2)
  • 空間復雜度O(n)

大家可以把兩個版本的代碼提交一下試試,就可以發現其差別了!

關于本題使用數組還是使用鏈表的性能差異,我在貪心算法:根據身高重建隊列(續集)中詳細講解了一波

總結

關于出現兩個維度一起考慮的情況,我們已經做過兩道題目了,另一道就是135. 分發糖果。

其技巧都是確定一邊然后貪心另一邊,兩邊一起考慮,就會顧此失彼。

這道題目可以說比135. 分發糖果難不少,其貪心的策略也是比較巧妙。

最后我給出了兩個版本的代碼,可以明顯看是使用C++中的list(底層鏈表實現)比vector(數組)效率高得多。

對使用某一種語言容器的使用,特性的選擇都會不同程度上影響效率。

所以很多人都說寫算法題用什么語言都可以,主要體現在算法思維上,其實我是同意的但也不同意。

對于看別人題解的同學,題解用什么語言其實影響不大,只要題解把所使用語言特性優化的點講出來,大家都可以看懂,并使用自己語言的時候注意一下。

對于寫題解的同學,刷題用什么語言影響就非常大,如果自己語言沒有學好而強調算法和編程語言沒關系,其實是會誤傷別人的。

這也是我為什么統一使用C++寫題解的原因,其實用其他語言java、python、php、go啥的,我也能寫,我的Github上也有用這些語言寫的小項目,但寫題解的話,我就不能保證把語言特性這塊講清楚,所以我始終堅持使用最熟悉的C++寫題解。 

而且我在寫題解的時候涉及語言特性,一般都會后面加上括號說明一下。沒辦法,認真負責就是我,哈哈。

本文轉載自微信公眾號「代碼隨想錄」,可以通過以下二維碼關注。轉載本文請聯系代碼隨想錄公眾號。

 

責任編輯:武曉燕 來源: 代碼隨想錄
相關推薦

2024-07-11 11:17:00

消息隊列Java

2022-11-30 09:54:57

網絡令牌身份驗證

2023-08-01 12:51:18

WebGPT機器學習模型

2024-01-02 12:05:26

Java并發編程

2024-01-19 08:25:38

死鎖Java通信

2024-02-04 00:00:00

Effect數據組件

2023-07-26 13:11:21

ChatGPT平臺工具

2023-01-10 08:43:15

定義DDD架構

2024-05-29 09:20:41

2024-08-21 08:27:30

擴展數據庫服務器

2023-09-12 07:26:46

2023-04-26 00:41:36

A/B測試郵件數量

2024-08-09 08:17:07

SSH服務器架構

2024-03-06 08:28:16

設計模式Java

2022-06-16 07:50:35

數據結構鏈表

2022-12-06 07:53:33

MySQL索引B+樹

2023-01-31 08:02:18

2023-10-06 14:49:21

SentinelHystrixtimeout

2022-07-13 08:16:49

RocketMQRPC日志

2023-05-05 06:54:07

MySQL數據查詢
點贊
收藏

51CTO技術棧公眾號

主站蜘蛛池模板: 久久精品播放 | 99视频在线免费观看 | 国产激情91久久精品导航 | 一级毛片网 | 午夜免费福利影院 | 另类视频在线 | 亚洲a一区二区 | 夜夜草视频 | 国产亚洲精品久久久优势 | 亚洲欧洲视频 | 国产精品免费视频一区 | 国产成人精品免费 | 中文字幕在线不卡播放 | 欧美一区二区三区大片 | 女女百合av大片一区二区三区九县 | 精品欧美在线观看 | 国产精品美女久久久久久不卡 | 国产人成精品一区二区三 | 91成人免费看 | 欧美美乳 | 国产午夜精品一区二区三区嫩草 | 成人在线免费观看 | 二区亚洲 | 欧洲一区二区视频 | 久久亚洲国产精品 | 欧美精品欧美精品系列 | 国产在线看片 | 亚洲黄色一区二区三区 | 在线播放第一页 | 成人国产精品久久久 | 午夜久久久久久久久久一区二区 | 欧美久 | 999久久久 | 99在线视频观看 | 中文字幕免费观看 | 天天爽天天干 | 久久久在线视频 | 一区二区视屏 | 久久大 | 国产精品一区二区三 | 精品国产乱码久久久久久老虎 |