LC406. 根据身高重建队列

我不是女神ヾ 2022-11-25 13:00 91阅读 0赞

假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(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\]\]

解题思路:

贪心加冒泡

首先把people根据身高从高到低,人数从小到大进行排序

然后把每个people和他前面的people进行比较,如果前面的people的身高高于他,那么就交换两位people

同时,要确保每个people前面的人数是正确的

class Solution {
    public:
        static bool cmp(vector<int>& a,vector<int>& b){
             if(a[0] != b[0]) return a[0] > b[0];
             else return a[1] < b[1];
        }
        vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
              vector<vector<int>> res = people;
              sort(res.begin(),res.end(),cmp);
              for(int index = 1;index < res.size();index++){
                 int j = index;
                 while(j){
                   if(res[j-1][0] > res[j][0] && 
                        res[j][1] < j  //这里控制位置){
                       swap(res[j],res[j-1]);
                       j--;
                   }else{
                       break;
                   }
                 }
              }
              return res;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，91人围观）

还没有评论，来说两句吧...

相关阅读

相关根据身高重建队列

406. 根据身高重建队列 > 假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people\[i\] = \[hi

Dear 丶/ 2024年04月03日 07:11/ 0 赞/ 55 阅读

相关 406. 根据身高重建队列

打卡!!!每日一题今天想通过一道题给大家分享一下一些常见的但是你却不一定了解的知识。题目描述： > 假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中

谁践踏了优雅/ 2023年10月11日 18:14/ 0 赞/ 34 阅读

相关【LeetCode刷题笔记（五十八）】之 406.根据身高重建队列

本文章由公号【开发小鸽】发布！欢迎关注！！！老规矩–妹妹镇楼： ![20200721223424816.JPG][] 一．题目（一）题干

淡淡的烟草味﹌/ 2023年10月07日 15:16/ 0 赞/ 67 阅读

相关（js）leetcode 406. 根据身高重建队列

最近感觉到自己在算法知识方面的匮乏，所以从今天起，每天一题leetcode，今天就先将flag立在这了。题目： > 假设有打乱顺序的一群人站成一个队列。每个人由一个

痛定思痛。/ 2022年12月21日 15:50/ 0 赞/ 100 阅读

相关 LeetCode 406. 根据身高重建队列 JAVA 回看

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

拼搏现实的明天。/ 2022年12月21日 10:56/ 0 赞/ 99 阅读

相关 LC406. 根据身高重建队列

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

我不是女神ヾ/ 2022年11月25日 13:00/ 0 赞/ 92 阅读

相关 406. 根据身高重建队列

文章目录 406. 根据身高重建队列示例 1：示例 2：解题思路代码 406

我会带着你远行/ 2022年11月03日 11:51/ 0 赞/ 122 阅读

相关 leetcode 406 根据身高重建队列

前言题目：[406. 根据身高重建队列][406.] 参考题解：[根据身高重建队列-代码随想录][-] -------------------- 提交代码

红太狼/ 2022年09月14日 09:54/ 0 赞/ 118 阅读

相关 leetcode 406. Queue Reconstruction by Height | 406. 根据身高重建队列（Java）

题目 [https://leetcode.com/problems/queue-reconstruction-by-height/][https_leetcode.com

╰半橙微兮°/ 2022年08月29日 10:15/ 0 赞/ 123 阅读

相关【LeetCode】406. 根据身高重建队列

题目链接：[https://leetcode-cn.com/problems/queue-reconstruction-by-height/description/][http

悠悠/ 2022年05月10日 15:12/ 0 赞/ 135 阅读