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

每天一道leetcode-406根据身高重建队列

作者头像
乔戈里
发布2019-01-11 11:59:14
1.9K0
发布2019-01-11 11:59:14
举报
文章被收录于专栏:Java那些事

406_(根据身高重建队列)Queue Reconstruction by Height

1 问题描述、输入输出与样例

1.1 问题描述

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

注意: 总人数少于1100人。

1.2 输入与输出

输入:

  • vector <pair >& people: 长度可变的结构体数组的引用 people</pair

输出:

  • vector <pair >: 重建之后的长度可变结构体数组</pair

1.3 样例

1.3.1 样例1

输入:[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]] 输出:[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

2 思路描述与代码

2.1 思路描述(排序重建法)

  1. 按身高 h 从大到小排列,身高相等按 k 从小到大排序
  2. 按照规则(当前(h, k)插入的位置为第 k 个元素)重建队列

比如输入:people = [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

  1. 排序后people = [[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]
  2. 按照规则(当前(h, k)插入的位置为第 k 个元素)重建队列
  • [7,0]插入第 0 个位置,有 ans = [[7,0]];
  • [7,1]插入第 1 个位置,有 ans = [[7,0], [7,1]];
  • [6,1]插入第 1 个位置,有 ans = [[7,0], [6,1], [7,1]];
  • [5,0]插入第 0 个位置,有 ans = [[5,0], [7,0], [6,1], [7,1]];
  • [5,2]插入第 2 个位置,有 ans = [[5,0], [7,0], [5,2], [6,1], [7,1]];
  • [4,4]插入第 4 个位置,有 ans = [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]];

2.2 代码

代码语言:javascript
复制
//函数中涉及到的c++知识
//pair<int, int> 可以理解为包含两个元素的结构体
//vector<pair<int, int>> 是个长度可变的结构体数组,c++里面称为容器
//ret_func_type func(vector<pair<int, int>>& name) 中的name是vector<pair<int, int>>容器的引用,可以理解为传入一个指针
//sort(g.begin(), g.end(), cmp) 对容器g的结构体按照cmp的排序规则排序,容器的起始数据的指针是 g.begin(),容器的末尾数据的指针是g.end()

//1. 按身高 h 从大到小排列,身高相等按 k 从小到大排序
//2. 重建队列
vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
    int len = people.size();
    vector<pair<int, int>> ans;
    //1. 按身高 h 从大到小排列,身高相等按 k 从小到大排序
    sort(people.begin(), people.end(), cmp);
    //2. 重建队列
    for( int i = 0; i < len; i++ ){
        ans.insert(ans.begin() + people[i].second, people[i]);
    }
    return ans;
}
//按身高 h 从大到小排列,身高相等按 k 从小到大排序
static bool cmp(const pair<int, int>& data1, const pair<int, int>& data2){
    return data1.first != data2.first ? data1.first > data2.first : data1.second < data2.second;
}

3 思考与拓展

3.1 思考

本题按照排序规则排序后,很容易找到重排后应插入的位置。

3.1.1 其他方法
3.1.1.1 排序+BIT(二分索引树)
  1. 按照以 h 从小到达, h 相同以 k 从小到达排序
  2. 遍历排序后的结构体数组,借助BIT(二分索引树)可以在O(logn)时间内找到未用的第 k 个位置。

比如输入:people = [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

  1. 排序后people = [[4,4], [5,0], [5,2], [6,1], [7,0], [7,1]]
  2. 按照规则(当前(h, k)插入的位置为第 k 个可用元素)重建队列
  • pos = [1,1,1,1,1,1], [4,4]插入第 4 + 1 个可用位置,有pos = [1,1,1,1,0,1], ans = [[-1,-1],[-1,-1],[-1,-1],[-1,-1],[4,4],[-1,-1]];
  • pos = [1,1,1,1,0,1], [5,0]插入第 0 + 1 个可用位置,有pos = [0,1,1,1,0,1], ans = [[5,0],[-1,-1],[-1,-1],[-1,-1],[4,4],[-1,-1]];
  • pos = [0,1,1,1,0,1], [5,2]插入第 2 - 1 + 1 个可用位置(相同元素需要减掉),有pos = [0,1,0,1,0,1], ans = [[5,0],[-1,-1],[5,2],[-1,-1],[4,4],[-1,-1]];
  • pos = [0,1,0,1,0,1], [6,1]插入第 1 + 1 个可用位置,有pos = [0,0,1,0,0,1], ans = [[5,0],[-1,-1],[5,2],[6,1],[4,4],[-1,-1]];
  • pos = [0,0,1,0,0,1], [7,0]插入第 0 + 1 个可用位置,有pos = [0,0,0,0,0,1], ans = [[5,0],[7,0],[5,2],[6,1],[4,4],[-1,-1]];
  • pos = [0,0,0,0,0,1], [7,1]插入第 0 + 1 个可用位置,有pos = [0,0,0,0,0,0], ans = [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
3.1.2 复杂度分析

方法

空间复杂度

时间复杂度

排序重建法

O(1)

平均O(nlogn),最差O(n^2)

排序+BIT(二分索引树)

O(n)

O(nlogn)

3.1.3 难点分析
  1. 找到合理的排序规则;
  2. 根据合理的规则对排序后的结构体数组重建

3.2 拓展

如果让你实现BIT(二分索引树)呢?

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-01-08,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 程序员乔戈里 微信公众号,前往查看

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

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 406_(根据身高重建队列)Queue Reconstruction by Height
  • 1 问题描述、输入输出与样例
    • 1.1 问题描述
      • 1.2 输入与输出
        • 1.3 样例
          • 1.3.1 样例1
      • 2 思路描述与代码
        • 2.1 思路描述(排序重建法)
          • 2.2 代码
          • 3 思考与拓展
            • 3.1 思考
              • 3.1.1 其他方法
              • 3.1.1.1 排序+BIT(二分索引树)
              • 3.1.2 复杂度分析
              • 3.1.3 难点分析
            • 3.2 拓展
            相关产品与服务
            容器服务
            腾讯云容器服务(Tencent Kubernetes Engine, TKE)基于原生 kubernetes 提供以容器为核心的、高度可扩展的高性能容器管理服务,覆盖 Serverless、边缘计算、分布式云等多种业务部署场景,业内首创单个集群兼容多种计算节点的容器资源管理模式。同时产品作为云原生 Finops 领先布道者,主导开源项目Crane,全面助力客户实现资源优化、成本控制。
            领券
            问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档