题目解析

题目的意思是数组每个元素有两个值[H, K]，第一个值是身高，第二个值是身高大于的此元素个数。比如下面的例子

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

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

在[5, 2]之前分别是[5, 0],[7, 0]故身高大于等于5(H)的元素共2个(K)

方法 快排+插入排序思想

通过观察可以发现，对于某个元素[H, K]来说它之前身高小于H的其他元素不会影响到它的K，比如对于[7, 1]来说[5, 0], [5, 2], [6, 1], [4, 4]不会影响K。因此首先把所以元素按照身高来排序，最后对于每一个元素来根据身高找到应该有K个比它高的元素在前面，这样就能找到这个元素的相对位置，也就是在K个比它大的元素后面。类似于插入排序。
时间复杂度O(n^2)

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
31
class Solution {
public:
    vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
        sort(people.begin(), people.end(), [](const auto & a, const auto & b) {
            int A = a.first, B = b.first; // [[A, aa], [B, bb]]
            int aa = a.second, bb = b.second;
            if (A == B) {
                return aa <= bb;
            }else {
                return A > B;
            }
        });
        for (int i = 0; i < people.size(); i++) {
            pair<int, int> num = people[i];
            int index = 0;
            int count = num.second;
            while(index < i && count > 0) { // 找到应该在哪些大于它的元素后面的位置
                if (num.first <= people[index].first) {
                    count--;
                }
                index++;
                if (count == 0) break;
            }
            for (int k = i; k > index; k--) { // 找到后，将它之后的元素向后挪一个位置出来
                people[k] = people[k-1];
            }
            people[index] = num;
        }
        return people;
    }
};