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

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 代码

//函数中涉及到的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 复杂度分析

3.1.3 难点分析

1. 找到合理的排序规则；
2. 根据合理的规则对排序后的结构体数组重建

3.2 拓展

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