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

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

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)。

上一篇:C语言面向对象(上):面向对象三大特性的实现


下一篇:jquery easyUi 配置默认页码