算法设计与分析-Week20

发表于

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

解题思路

本题给出一个随机people数组，每个people由两个数组成，第一个数 h 表示people的身高，第二个数 k 表示在该people前面有 k 个人不比他矮，按这个要求重排people数组。
首先选出数组中最高的people，按他们的 k 值作为他们的下标插入到结果数组中，然后选出次高的people，同样按他们的 k 值作为他们的下标插入到结果数组中，以此类推。该做法基于两个原理：1.后插入的people由于身高比先插入的低，因此不管怎么插入都不会使得先插入的people违反要求；2.插入people时，结果数组中的people都是比自己高的，因此按 k 值为下标插入即可满足要求。

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
        sort(people.begin(), people.end(), [](pair<int, int> a, pair<int, int> b) {
            if(a.first > b.first) return true;
            else if(a.first == b.first) return a.second < b.second;
            return false;
        });
        vector<pair<int, int>> res;
        for(pair<int, int> p : people) {
            res.insert(res.begin() + p.second, p);
        }
        return res;
    }
};
0%