There are (n) people, we want them line up in the following way.
Given a two-dimensional array: (people[n][2]), where (people[i]=[h_i][k_i]), (h_i) means the height of (i)-th person, (k_i) means there are (k_i) people who are the same height as person (i) or taller than person (i) stand in front of person (i). So there are actually (k_i) or more people stand in front of person (i).
According to the two-dimentional array, line them up. It’s promised that them can be lined up.
people =([[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]])
answer =([[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]])
Firstly, let’s consider a simpler case: people’s height differs. No two people are the same height.
Assume there are a array (line[n]). We want to put everyone in this line. When we put (people[i]=[h_i][k_i]), assuming no one taller than him has been lined. We need to reserve (k_i) spaces in front of him for those (k_i) people who are higher than him. So we put person (i) at the (k_i+1)-th empty position.
How to ensure “no one taller than him has been lined”? That’s sample, just put them in the line in ascending order of height.
Now we consider how to handle people who have same height.
For person (i), (j), we assume their height are the same. Without loss of generality, we assume (k_i
Sort (people) array according to (h_i) as the first keyword in ascending order and (k_i) as the second keyword in descending order.
Put the sorted (people[i]) in the (k_i+1)-th position in turn.
The detailed code is as follows
public class p406 {
public int[][] reconstructQueue(int[][] people) {
int num = people.length;
Arrays.sort(people, new Comparator() {
public int compare(int[] t1, int[] t2) {
return t1[0] == t2[0] ? t2[1] - t1[1] : t1[0] - t2[0];
}
});
int[][] ans = new int[num][];
for (int[] person : people) {
int space = person[1] + 1;
for (int i = 0; i < num; i++) {
if (ans[i] == null) {
space--;
}
if (space == 0) {
ans[i] = person;
break;
}
}
}
return ans;
}
}
Time complexity: (O(\log n)) for sort, (O(n^2)) for going through (people) array and find corresponding location for each person. So the total time complexity is (O(n^2)).
Space complexity: Sorting is implemented by recursive calls. So the time complexity is (O(\log n)).
Original: https://www.cnblogs.com/liuzhch1/p/16183496.html
Author: liuzhch1
Title: LeetCode 406.根据身高重建队列 | 解题思路及代码
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/606684/
转载文章受原作者版权保护。转载请注明原作者出处！