406. Queue Reconstruction by Height

Leetcode 問題: 406. Queue Reconstruction by Height
Categories:
Tags:

題目

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).

給予一個使用者陣列，陣列中包含每個 使用者的身高 以及 使用者希望排隊前面有多少人 跟他一樣高或比他高

例如：[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]

陣列 身高 希望有多少人跟他一樣高或比他高
[7,0] 7 0
[4,4] 4 4
[7,1] 7 1
[5,0] 5 0
[6,1] 6 1
[5,2] 5 2

目標要找到符合所有人的 身高排序 以及 希望的前方障礙物

[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] 最後排序

索引順序 1 2 3 4 5 6
使用者 [5,0] [7,0] [5,2] [6,1] [4,4] [7,1]
使用者身高 5 7 5 6 4 7
前面有多少人跟他一樣高或比他高 0 0 2 1 4 1

Example

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.

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

答案

  1. 將身高由 高到低排序，若身高相同，前面 需要比他高的人越少 排越前面
  2. 因為使用者陣列是按照身高排序，所以越前面的人身高越高，越沒有阻礙，「後面的使用者」身高會低於或等於「前面的使用者」，看那個使用者前面需要多少阻礙，將他安排在指定的位置

JavaScript

/**
 * @param {number[][]} peopleList
 * @return {number[][]}
 */
var reconstructQueue = function(peopleList) {
    if (!peopleList || peopleList.length == 0 || peopleList[0].length == 0) {
        // 如果沒有傳入人的陣列資料
        return [];
    }

    // 排序身高大小(身高越高排前面)
    peopleList.sort((a, b) => {
        if (a[0] > b[0]) {
            // 當 a[0] 數字比 b[0] 大，a 較大排前面
            return -1;
        } else if (a[0] < b[0]) {
            // 當 a[0] 數字比 b[0] 小，a 較笑排後面
            return 1;
        } else {
            // a[0] 數字 與 b[0] 一樣大，表示身高一樣，將前面阻礙需要越少的放前面
            if (a[1] < b[1]) {
                // 當 a[1] 數字比 b[0] 小，a 需要較少人比他高，a 排前面
                return -1;
            } else {
                // 當 a[1] 數字比 b[0] 大，a 需要較多人比他高，a 排後面
                return 1;
            }
        }
    });

    // 排序的使用者清單
    let orderPeopleList = [];

    peopleList.forEach((currentPeople) => {
        // 目前使用者，前面允許多少人身高「跟他一樣或比他高」
        let currentPeopleAllowHigherPeopleCount = currentPeople[1];
        // 因為使用者陣列是按照身高排序，所以越前面的人身高越高，越沒有阻礙
        // 「後面的使用者」身高會低於或等於「前面的使用者」，看那個使用者前面需要多少阻礙，將他安排在指定的位置
        orderPeopleList.splice(currentPeopleAllowHigherPeopleCount, 0, currentPeople);
    });

    return orderPeopleList;
};

參考資料