您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

2022-3-21 Leetcode 406.根据身高重建队列

在这里插入图片描述
在这里插入图片描述
先给数组排序,第一个数较大的在前面,如果第一个数字相同,第二个数字比较小的在前面。
之后再通过插入调整顺序,从头开始,按照第二个数字插入。
为什么这样做是正确的?
因为第二个数字是新插入的人的前面有几个人的身高高于等于新插入的人。在这个人插入的时候其他的人都比他高或者和他一样高,依照第二个数字插入就行了。
之后插入的人都是不如这个人高的,没有影响。

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>> &people) {
        auto cmp = [&](vector<int> &a, vector<int> &b) {
            if (a[0] != b[0]) {
                return a[0] > b[0];
            }
            return a[1] < b[1];
        };
        sort(people.begin(), people.end(), cmp);
        vector<vector<int>> ans;
        for (vector<int> p : people) {
            ans.insert(ans.begin() + p[1], p);
        }
        return ans;
    }
};

作者:dodo_1202
链接:https://leetcode-cn.com/problems/queue-reconstruction-by-height/solution/pai-xu-yu-chu-li-tan-xin-zong-jie-xia-da-lbu6/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进