Leetcode-406 Queue Reconstruction by Height

发表于 | 分类于 | 次

Queue Reconstruction by Height

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Note:
The number of people is less than 1,100.

Example 1

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

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

解题思路

身高 h 最低的那些人其位置由 k 决定，因为他前面只能有 k 个不比他矮的人。身高最低的那些人站好位置后，在剩下的位置中排列剩下的人，是同样的问题，只不过每个位置的索引只包含空闲位置。

复杂度分析

  • 时间复杂度：$O(n^2)$，每个人都要挑选一个与 k 对应的空闲位置。
  • 空间复杂度：$O(n)$，存储结果。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
	vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
		sort(people.begin(), people.end()); //按身高从小到大排序
		vector<vector<int>> res(people.size());

		for (auto &p : people) {
			int i = 0, j = 0;
			while (j <= p[1]) { //寻找第 p[1] 个空闲位置
				//位置i空闲或有一个同样身高的人,在当前是一个有效位置
				if (res[i].size() != 2 || res[i][0] == p[0]) ++j;
				++i;
			}
			swap(res[i - 1], p);
		}
		return res;
	}
};