【经典算法题】根据身高重建队列

Leetcode 0406 根据身高重建队列

问题描述：Leetcode 0406 根据身高重建队列

分析

• 这一题存在两种做法。

方法1

• 0~n-1，一共n个位置，我们需要考虑每个人放在哪个位置。

• 将people按照第一维升序、第二维降序的顺序排序，然后依次从前往后考虑每一个二元组。

• 假设当前考察的是第i个二元组 ( h , k ) (h, k) (h,k)，首先让k++，说明这个人身高是第k大的。

• 假设第i个二元组的身高严格大于第i-1个二元组的身高，则我们需要在还没有放入人的位置中找到第k位置对应的下标，然后将第i个人（二元组）放到这个位置。

• 假设第i个二元组的身高等于第i-1个二元组的身高，则我们仍按照上面的方式操作，结果仍然正确，因为此时第i个二元组一定放在第i-1个二元组左边(因为第i个二元组k更小)。第i-1个人左边大于等于他的人数没有改变（因为等于也符合条件）。

• 考虑上面的分析中存在什么操作（类似于AcWing 244. 谜一样的牛）：

  （1）从剩余的数（对应的位置索引）中，找出第k大的数；

  （2）删除某个数（索引）；

• 我们可以使用一个数组记录每个数据是否被使用过，记为数组a，a[i]=1表示位置i没有被使用过，a[i]=0表示位置i已经被人占了；设 s u m ( x ) = ∑ a [ i ] , 1 ≤ i ≤ x sum(x)=\sum a[i], 1 \le i \le x sum(x)=∑a[i],1≤i≤x则上面的操作等价于（代码实现中a不需要定义出来）：

• 则上面的操作等价于：

  （1）找到一个最小的x，使得sum(x)==k；

  （2）将a[x]置为0，代表该高度已经被使用过。

• 第（2）个操作相当于单点加，第（1）个操作相当于区间和，可以使用树状数组解决。

• 对于第（1）个操作，因为sum(x)是x的一个单调递减函数，因此可以使用二分求解。

方法2

• 将people按照第一维降序、第二维升序的顺序排序，然后依次从前往后考虑每一个二元组。

• 假设记录答案的数组为res，对于第i个二元组 ( h , k ) (h, k) (h,k)，将其插入res[k]位置即可。

• 上图参考的网址：网址

代码

• C++

// 方法1
class Solution {
public:
    int n;
    vector<int> tr;

    int lowbit(int x) {
        return x & -x;
    }

    void add(int x, int c) {
        for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
    }

    int query(int x) {
        int res = 0;
        for (int i = x; i; i -= lowbit(i)) res += tr[i];
        return res;
    }

    vector<vector<int>> reconstructQueue(vector<vector<int>> &people) {
        n = people.size();
        tr.resize(n + 1);  // 树状数组下标必须从1开始
        for (int i = 1; i <= n; i++) tr[i] = lowbit(i);

        sort(people.begin(), people.end(), [](vector<int> a, vector<int> b) {
            if (a[0] != b[0]) return a[0] < b[0];  // 按照第一维升序
            return a[1] > b[1];  // 按照第二维降序
        });

        vector<vector<int>> res(n);
        for (auto p : people) {
            int k = p[1] + 1;
            int l = 1, r = n;
            while (l < r) {
                int mid = l + r >> 1;
                // query(mid)返回a[1..mid]中1的个数，1表示该位置没被占用
                if (query(mid) >= k) r = mid;
                else l = mid + 1;
            }
            res[r - 1] = p;  // a[1]表示第0个位置的占用情况
            add(r, -1);
        }
        return res;
    }
};

// 方法二
class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>> &people) {

        // 按照第一维降序，第二维升序排列
        sort(people.begin(), people.end(), [](const vector<int> &a, const vector<int> &b) {
            if (a[0] == b[0]) return a[1] < b[1];
            return a[0] > b[0];
        });

        vector<vector<int>> res;
        for (auto &p : people) {
            res.insert(res.begin() + p[1], p);
        }

        return res;
    }
};

• Java

// 方法二
public class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (o1, o2) -> {
            // 如果身高相等(o1[0] == o2[0]) , 按照K降序排列(o2[0] - o1[0])
            return o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0];
        });

        List<int[]> list = new ArrayList<>();
        for (int[] p : people) {
            list.add(p[1], p);
        }

        return list.toArray(new int[0][0]);
    }
}

• 时间复杂度： O ( n × l o g ( n ) ) O(n\times log(n)) O(n×log(n))，n为人数。

• 空间复杂度： O ( 1 ) O(1) O(1)。