leetcode：406. 根据身高重建队列

题目

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

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

示例：

输入：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]] 是重新构造后的队列。

输入：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]]

解答 & 代码

以 people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] 为例

排序：对 people 按 hi = people[i][0] 降序排列，按 ki=people[i][1] 升序排列。即排序后，升高高的人排在前面；如果身高相同，则 k 小的排在前面（k 是前面身高大于或等于它的人数）

排序后数组变为 people = [[7, 0], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4]]

遍历排序后的 people 数组，依次将每个元素插入结果数组 result，people[i] 插入的位置为 ki = people[i][1]，即

[7, 0] 插入在 result 第 0 个位置，插入后 result = [[7, 0]]
[7, 1] 插入在 result 第 1 个位置，插入后 result = [[7, 0], [7, 1]]
[6, 1] 插入在 result 第 1 个位置，插入后 result = [[7, 0], [6, 1], [7, 1]]
[5, 0] 插入在 result 第 0 个位置，插入后 result = [[5, 0], [7, 0], [6, 1], [7, 1]]
[5, 2] 插入在 result 第 2 个位置，插入后 result = [[5, 0], [7, 0], [5, 2], [6, 1], [7, 1]]

[4, 4] 插入在 result 第 4 个位置，插入后 result = [[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]]

class Solution {
private:
  // 快排分割函数
  int partition(vector<vector<int>>& arr, int left, int right)
  {
      int randomIdx = random() % (right - left + 1) + left;
      swap(arr[left], arr[randomIdx]);
      vector<int> pivot = arr[left];
      while(left < right)
      {
          while(left < right && (arr[right][0] < pivot[0] || 
                              (arr[right][0] == pivot[0] && arr[right][1] >= pivot[1])))
              --right;
          arr[left] = arr[right];
          while(left < right && (arr[left][0] > pivot[0] ||
                              (arr[left][0] == pivot[0] && arr[left][1] <= pivot[1])))
              ++left;
          arr[right] = arr[left];
      }
      arr[left] = pivot;
      return left;
  }
  // 快速排序
  void quickSort(vector<vector<int>>& arr, int left, int right)
  {
      if(left >= right)
          return;
      int pivot = partition(arr, left, right);
      quickSort(arr, left, pivot - 1);
      quickSort(arr, pivot + 1, right);
  }
public:
  vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
      int len = people.size();
      // 1. 对 people 数组进行排序，排序规则：按 hi 降序，ki 升序
      //    即身高 h 高的排前面；若身高 h 相同，则 k 小的排前面（k 是前面身高大于或等于它的人数）
      quickSort(people, 0, len - 1);
      vector<vector<int>> result;        // 结果数组
      // 2. 遍历排序后的 people 数组，依次将每个元素插入结果数组，插入规则：
      //       插入的位置为 ki = people[i][1]
      for(int i = 0; i < len; ++i)
          result.insert(result.begin() + people[i][1], people[i]);
      return result;
  }
};

复杂度分析：设数组长度为 N

时间复杂度：
- 数组快速排序时间复杂度 O(NlogN)
- 排序后，每次插入时间复杂度 O(N)，N 次插入，总体时间复杂度
空间复杂度 O(log N)：
- 快排的递归函数栈空间复杂度 O(logN)（快速排序就相当于二叉树的前序遍历，空间复杂度即递归深度取决于树的高度）
- 结果数组的空间复杂度不计入

执行结果：

执行结果：通过
执行用时：144 ms, 在所有 C++ 提交中击败了 42.80% 的用户
内存消耗：12.3 MB, 在所有 C++ 提交中击败了 40.79% 的用户

hot 100

[中等] 406. 根据身高重建队列

题目

解答 & 代码