0406._Queue_Reconstruction_By_Height

发表于 分类于 ， ，

406. Queue Reconstruction By Height

难度: medium

刷题内容

原题连接

内容描述

假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。

注意：
总人数少于1100人。

示例 1:

1
2
3
4
5
输入:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

输出:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

解题方案

思路 1
**- 时间复杂度: O(N²)**- 空间复杂度: O(N)**

贪心算法
思路
个子矮的人的位置不会影响到其他人，他的位置不会影响到其他人。

操作步骤

  1. 对人群排序，由高到低，身高相同再由低到高
  2. 建立一个空队列
  3. 对排序后的人群进行遍历，将当前遍历的人 按照他的索引（n）插入到队列第n的位置

代码：

1
2
3
4
5
6
7
8
var reconstructQueue = function(people) {
  people.sort((a, b) => ((b[0] - a[0]) || (a[1] - b[1])));
  let queue = [];
  people.forEach(person => {
    queue.splice([person[1]], 0, person);
  })
  return queue
};