阅读量:3
代码解决
class Solution { public: // 定义排序规则：首先按身高降序排序，如果身高相同则按k值升序排序 static bool cmp(const vector<int>&a, const vector<int>&b) { if (a[0] == b[0]) return a[1] < b[1]; // 如果身高相同，按k值升序排序 return a[0] > b[0]; // 否则按身高降序排序 } vector<vector<int>> reconstructQueue(vector<vector<int>>& people) { // 先按照自定义规则排序 sort(people.begin(), people.end(), cmp); list<vector<int>> res; // 用链表来存储结果以方便插入操作 // 遍历排序后的列表 for (int i = 0; i < people.size(); i++) { int position = people[i][1]; // 获取当前人的k值 list<vector<int>>::iterator it = res.begin(); // 定义迭代器指向链表开头 // 找到插入位置 while (position--) { it++; } // 插入到链表中的相应位置 res.insert(it, people[i]); } // 将链表转换为向量并返回 return vector<vector<int>>(res.begin(), res.end()); } }; 这段代码定义了一个名为`Solution`的类，其中包含两个成员函数：一个静态比较函数`cmp`和一个成员函数`reconstructQueue`。下面是对这两个函数的解释：
1. `cmp`函数：
这是一个静态比较函数，用于定义排序规则。它接受两个`vector<int>`类型的参数`a`和`b`，并返回一个布尔值。这个函数首先比较两个向量的第一个元素（身高），如果它们相等，则比较第二个元素（k值）。排序规则是：优先按照身高降序排序，如果身高相同，则按照k值升序排序。
2. `reconstructQueue`函数：
这个函数的目的是根据给定的规则重新排列一个人群的队列。它接受一个`vector<vector<int>>`类型的参数`people`，其中每个内部向量包含两个整数：第一个整数表示身高，第二个整数表示该人的k值。函数返回一个新的`vector<vector<int>>`类型的队列，其中的元素按照身高降序、k值升序的规则排列。
函数的具体实现步骤如下：
- 使用`sort`函数对`people`向量进行排序，排序规则由静态比较函数`cmp`提供。
- 定义一个链表`res`来存储最终的结果，因为链表允许在任意位置插入元素。
- 遍历排序后的`people`列表，对于每个人：
- 获取当前人的k值（即插入位置）。
- 定义一个迭代器`it`指向链表的开头。
- 通过循环将迭代器移动到插入位置的前一个位置。
- 使用`insert`函数将当前人的信息插入到链表的正确位置。
- 最后，将链表转换为向量并返回。这里使用了链表到向量的构造函数，它接受两个迭代器参数，表示转换的范围。
总结来说，这段代码实现了一个根据特定规则对人群进行排序的功能，规则是先按身高降序，如果身高相同则按k值升序。排序完成后，返回一个新的队列，保持了这种顺序。
