【经典算法题】根据身高重建队列
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)。