Leetcode406. 根據身高重新構造隊列

Leetcode406. Queue Reconstruction by Height

題目

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Note:

The number of people is less than 1,100.

Example:

Input:

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

解題分析

一拿到這道題，可能剛開始會是毫無頭緒的，不知從何下手。但粗略想一下，可能會覺得應該将他們按身高排序。

但問題的關鍵在于要如何根據他們的身高來确定位置，進而實作要求的隊列。一種想法是，将他們按身高從小到大排序，然後按照比他們高的人數對應插入位置，如果位置不為空，就周遊數組找到不為空的位置然後插入。之後再周遊數組的每個元素，如果他所在位置在他前面比他高的人數不等于他實際的位置，那麼就往後周遊數組，找到第一個比他高的進行位置的交換。這樣做不是不可以，但是可能顯得有些過于麻煩了。

那有什麼更好的做法呢？這裡我們用到了vector的insert函數，它表示在對應位置插入元素，如果該位置有元素，就自動将已插入的元素往後移。說實話，這個函數并不怎麼用，以至于我都忘記了。結合題目的要求，我們可以往vector裡面對應位置插入身高比較高的元素，然後後面如果有位置重疊，就自動将身高比較高的元素往後挪，這樣問題就順利解決了，比上面一種做法也簡單了許多。

源代碼

class Solution {
public:
    vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
        int i, size = people.size();
        vector<pair<int, int>> v;
        sort(people.begin(), people.end(), [](const pair<int, int>& x, const pair<int, int>& y) -> int {
            return (x.first > y.first) || (x.first == y.first && x.second < y.second);
        });
        for (i = ; i < size; i++) {
            v.insert(v.begin() + people[i].second, people[i]);
        }
        return v;
    }
};
           

以上是我對這道問題的一些想法，有問題還請在評論區讨論留言~