【Leetcode】 406. 根据身高重建队列

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

示例 1：

输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：

• 编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
• 编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
• 编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
• 编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
• 编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
• 编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
  因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

示例 2：

输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

提示：

1 <= people.length <= 2000
0 <= hi <= 106
0 <= ki < people.length
1
2
3

题目数据确保队列可以被重建

---

谈谈自己新接触的cpp迭代器（从大佬AC代码种学到的，不喜勿喷），让我有一种在学java时，遇到的hasNext()和next（）函数？
相比起使用vector数组，list能使时间复杂度明显性的降低！
list底层属于双向链表，找了一堆英文，瞎总结的！

---

AC（优选):

/*
 * @lc app=leetcode.cn id=406 lang=cpp
 *
 * [406] 根据身高重建队列
 */

// @lc code=start
class Solution {
private:
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        if(a[0] == b[0])
            return a[1] < b[1];
        return a[0] > b[0];
    }
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), cmp);
        list<vector<int>> que;
        for(int i = 0; i < people.size(); i++) {
            int position = people[i][1];
            std::list<vector<int>>::iterator it = que.begin();
            while(position--) {
                it++;
            }
            que.insert(it, people[i]);
        }
        return vector<vector<int>>(que.begin(), que.end());
    }
};
// @lc code=end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

AC（纯数组实现）:

/*
 * @lc app=leetcode.cn id=406 lang=cpp
 *
 * [406] 根据身高重建队列
 */

// @lc code=start
class Solution {
private:
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        if(a[0] == b[0])
            return a[1] < b[1];
        return a[0] > b[0];
    }
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), cmp);
        vector<vector<int>> que;
        for(int i = 0; i < people.size(); i++) {
            int position = people[i][1];
            que.insert(que.begin() + position, people[i]);
        }
        return que;
    }
};
// @lc code=end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

这是因为vector实际是个动态数组，底层是普通数组。数组在插入的过程中，如果插入的元素大于预先普通数组的大小，底层会实现一个扩容的操作，申请两倍于原先普通数组的大小空间，然后将原先数组上的数据拷贝到扩容的数组上！

---

C++中的迭代器（iterator）是一种通用的概念，用于访问和遍历容器中的元素。迭代器可以像指针一样用于遍历容器元素，它提供了一组操作符和函数，使其与指针类似。

以下是使用迭代器的一般步骤：

1. 定义迭代器变量：

//定义一个int类型的vector
std::vector<int> myvector (5);
//定义一个iterator变量
std::vector<int>::iterator it;
1
2
3
4

2. 初始化迭代器：

it = myvector.begin(); //指向第一个元素
1

3. 使用迭代器访问容器元素：

*it = 10; //访问第一个元素
1

4. 遍历容器元素：

for (it = myvector.begin(); it != myvector.end(); ++it)
    std::cout << *it << ' ';
1
2

其中，begin()和end()函数用于返回迭代器，指向容器的开始和结束位置。运算符*用于解引用迭代器，获取指向的元素。运算符++用于将迭代器向前移动一个位置。

需要注意的是，不同类型的容器可能会定义不同类型的迭代器，例如，vector和list容器有不同的迭代器类型，需要根据具体容器的类型来定义对应的迭代器类型。

---

Cpp中的list是双向链表，它的底层实现方式是通过节点(node)来存储数据，每个节点包括两个指针，分别指向前一个节点(prev)和后一个节点(next)，以及一个数据域(data)，用于存储节点的数据。在list中，我们只需要记录头部指针和尾部指针，就可以方便地对整个链表进行操作。

对于list的使用方法，首先需要包含头文件。以下是一些基本操作：

1. 在list的末尾添加元素

list<int> nums;
nums.push_back(1); // 在末尾添加元素
nums.push_back(2);
nums.push_back(3);
1
2
3
4

2. 在list的开头添加元素

list<int> nums;
nums.push_front(3); // 在开头添加元素
nums.push_front(2);
nums.push_front(1);
1
2
3
4

3. 遍历list中的元素

list<int> nums{1,2,3,4,5};
for(auto it = nums.begin(); it != nums.end(); ++it){
    cout<<*it<<" ";
}
1
2
3
4

4. 在list中插入元素

list<int> nums{1,2,3,5};
auto it = nums.begin(); // 定位需要插入的位置
++it; // 向后移动一个位置
nums.insert(it, 4); // 在it位置插入元素4，注意it需要传入迭代器
1
2
3
4

5. 在list中删除元素

list<int> nums{1,2,3,4,5};
auto it = nums.begin(); // 定位需要删除的位置
++it; // 向后移动一个位置
nums.erase(it); // 删除it位置的元素，注意it需要传入迭代器
1
2
3
4

还有其他一些操作，如清空list、获取list的大小等，可以查看list的官方文档进行学习。