题目详情

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

注意：

总人数少于1100人。

示例

输入:

[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

输出:

[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

解题思路

此题放在贪心算法中，是用贪心的思想来解题

首先对数组按照第一个元素height 降序排列

此时数组前面的元素的height 大于后面元素的height

然后以每个元素的k值插入到返回数组里，比如元素的k为 2，就插到返回数组的下标为2的位置。

以题目的例子来进行操作

这是原来的数组

people = [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

按照height进行降序排序之后

people = [[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]] 

对降序后的people数组  从第一个元素开始 把每个元素加入到返回数组

加入的策略是， 按照每个元素的k 来插入到下表为k的位置上

1.

插入  [7,0]

插入到离开始位置偏移了0个距离的位置。

result = [[7,0]]

2.

插入  [7,1]

插入到离开始位置偏移了1个距离的位置，即插入到[7,0]的后面。

result = [[7,0], [7,1]]

3.

插入  [6,1]

插入到离开始位置偏移了1个距离的位置，即插入到[7,0]的后面。

result = [[7,0], [6,1], [7,1]]

4.

插入  [5,0]

插入到离开始位置偏移了0个距离的位置，即插入到[7,0]的前面。

result = [[5,0], [7,0], [6,1], [7,1]]

5.

插入  [5,2]

插入到离开始位置偏移了2个距离的位置，即插入到[7,0]的后面。

result = [[5,0], [7,0], [5,2], [6,1], [7,1]]

6.

插入  [4,4]

插入到离开始位置偏移了4个距离的位置，即插入到[6,1]的后面。

result = [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

得到最终结果

result: [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

贪心证明

把每个元素以k 插进去，因为是按照height 来由大到小插进去的，把元素插进第k位置， 插入后前面的height 是比当前插入元素大（因为已经插入的元素height大或者相等）， 这就满足了排在前面身高大于或等于的人数为k，但是要注意我现在说的数组并不是最终结果的数组，而是插入这个元素形成的中间数组。是相对于中间数组来说的。

那么有一个问题了， 最终结果里 [6,1] 前面有[5,0]， [5,1]，这些height是小于6的，但是排在[6,1]前面, 这些元素是在[6,1]加进去之后加进去的，这些加进去的元素对 [6,1] 满足的条件（排在前面身高大于或等于的人数为k）会有影响吗？答案是不会的，因为在[6,1]加进去的元素的height 是小于6的无论加在哪个地方对 [6,1]的 k 不会改变。

综上，此算法能求出结果

AC代码

class Solution {

public:

    vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {

        vector<pair<int, int>> result;

        //  lambda 表达式

        sort(people.begin(), people.end(), [](pair<int, int> a, pair<int, int> b){

            return a.first > b.first || (a.first == b.first && a.second < b.second);

        });

        for (auto i: people) {

            result.insert(result.begin() + i.second, i);

        }

        return result;

    }

};

总结

因为在前面贪心的过程中插入的元素不会对前面已经插入元素的k造成印象，所以才能贪心，否则就可能用到其他的方法来解题了。

巴特西

LeetCode406 queue-reconstruction-by-height详解

题目详情

解题思路

贪心证明

AC代码

总结

最新文章

热门文章