根据身高重建队列

题目

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

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

具体思路

• 按照要求插入的位置排列，在插入一个个元素之后，容易重新打乱；
• 按照身高排序，可以保证插入的位置之前都符合要求，而且不会干扰已经排好的结果。

关键点：按照什么方式来进行对原始数组进行排序

代码实现

class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        if (a[0] == b[0])
            // [7,0]排在[7,1]前面,降序排列
            return a[1] < b[1];
        // 升序排列
        return a[0] > b[0];
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), cmp);
        vector<vector<int>> res;
        for (int i = 0; i < people.size(); i++) {
            // 位置是从当前开始res.begin(),到people[i][1]的位置,后一个是偏移量
            res.insert(res.begin() + people[i][1], people[i]);
        }
        return res;
    }
};

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (x, y) -> {
            return x[0] == y[0] ? x[1] - y[1] : y[0] - x[0];
        });

        // 70 71 61 50 52 44

        // 70 
        // 70 71
        // 70 61 71
        // 50 70 61 71
        // 50 70 52 61 71
        // 50 70 52 61 44 71

        List<List<Integer>> res = new ArrayList<>();
        res.add(Arrays.asList(people[0][0], people[0][1]));
        for (int i = 1; i < people.length; i++) {
            res.add(people[i][1], Arrays.asList(people[i][0], people[i][1]));
        }
        int[][] result = res.stream()
                .map(list -> list.stream().mapToInt(Integer::intValue).toArray())
                .toArray(int[][]::new);
        return result;
    }
}