前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >leetcode-406 根据身高重建队列

leetcode-406 根据身高重建队列

作者头像
用户3578099
发布2020-11-19 17:24:28
6590
发布2020-11-19 17:24:28
举报
文章被收录于专栏:AI科技时讯

题目

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

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

思路

首先,大体上按照身高由大到小的顺序进行排序,来保证之后插入的时候我们目标数组的每一个元素都大于我们要插入的元素。之后就好办了,根据前面有几个比他高的人来判断我要将新元素插入到哪个位置,比如前面没有比他高的人自然就插入到最前面的位置,python的insert函数就像量身为其打造一般。

还有一点需要注意,在身高相同的情况下,前方比本身身高高的人数少的要排在前面。假如两个人为(x, 0), (x, 1),那么为了让后面的人找到比他高的人(也就是(x, 0)),那么就需要先将(x, 0)插入其中。不是最高身高的情况也是类似的。

于是,我们就需要进行两次排序,像箱子排序一样。所幸,python的sort函数是稳定的,于是我们就先将前方人数进行升序排序,再将身高进行降序排序。之后逐一插入就大功告成了

代码语言:javascript
复制
class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        # 先按照身高排序,然后按照k升序排
        # 最后进行index 插入
        people.sort(key = lambda x: [-x[0], x[1]])
        res = []
        for p in people:
            res.insert(p[1], p)  # 基于后面的值作为index 插入到list中
        return res
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-11-16,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 AI科技时讯 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档