406. 根据身高重建队列

https://leetcode-cn.com/problems/queue-reconstruction-by-height/

解法一：

先将vector排序,按h排序(降序),h值相等按k值排(升序)

第一次:[7,0]

第二次:[7,0],[7,1]

第三次:[7,0],[6,1],[7,1]

第四次:[5,0],[7,0],[6,1],[7,1]

第五次:[5,0],[7,0],[5,2],[6,1],[7,1]

第六次:[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]

算法的简单解释就是:排序处理后,h值大的放前面,因为越大的数限制越小;而越小的数由于要保证前面有k个比他大的数,限制越多. 对于h值相等的数,就看k值,因为小的数不会影响大数的k,所以先放大数之后,小数就可以直接放到vector的第k个位置,而不会影响别人. 这里用到sort的三参数版本,最后一个参数为比较函数 http://zh.cppreference.com/w/cpp/algorithm/sort

template< class RandomIt, class Compare >
void sort( RandomIt first, RandomIt last, Compare comp );

first, last - 要排序的元素范围

comp - 比较函数对象（即满足比较 (Compare) 概念的对象），若第一参数小于（即先序于）第二参数则返回 true 。
比较函数的签名应等价于如下者：

 bool cmp(const Type1 &a, const Type2 &b);

签名不必拥有 const & ，但函数对象必须不修改传递给它的对象。
类型 Type1 与 Type2 必须使得 RandomIt 类型的对象能在解引用后隐式转换到这两个类型。

c++:

vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
    //先对people做排序处理,其中比较函数使用lambda表达式
    sort(people.begin(), people.end(), [](const pair<int, int> p1, const pair<int, int> p2)
        { return p1.first > p2.first || (p1.first == p2.first && p1.second < p2.second); });
    vector<pair<int, int>> res;
    for (auto p : people) {  //从头遍历people,将p按k值插入res
        res.insert(res.begin()+p.second, p);
    }
    return res;
}

py：重点在于lambda表达式的骚操作

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        #用sort排序，lambda表达式表示按第一个元素降序，第一个相等则按第二个升序
        people = sorted(people, key=lambda x:(-x[0], x[1]))
        res = []
        for i in range(len(people)):
            k = people[i][1]  #取people成员的k值
            res.insert(k, people[i])  #按k值插入
        return res

上一页401-600 下一页407.接雨水II

最后更新于5年前