题目大意：
根据身高重建队列
假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。
注意：
总人数少于1100人。
示例 ：
输入: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]] 输出: [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=406
解题思路分析：
做本题之前可以先参照一下这道简单题目：LEETCODE 1389. Create Target Array in the Given Order 解题思路分析
这道题我们需要先对数组进行排序，身高高的排在前面，身高相同时，数组中第二位数小的一方排在前面。排序完成之后，我们新建一个数组，然后按顺序从排序好的数组中取每一个数组，使用该数组的第二位数字作为下标插入到新的数组即可。我们使用题目的例子还说明一下，先将数组排序：
[[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]
接下来我们开始向新的数组中插入：
[[7,0]] // 插入[7,0]到第0位 [[7,0], [7,1]] // 插入[7,1]到第1位 [[7,0], [6,1], [7,1]] // 插入[6,1]到第1位 [[5,0], [7,0], [6,1], [7,1]] // 插入[5,0]到第0位 [[5,0], [7,0], [5,2], [6,1], [7,1]] // 插入[5,2]到第2位 [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]] // 插入[4,4]到第4位
接下来我们简单的证明一下上述逻辑。我们将数组排序之后，保证身高高的排在前面，身高相同的人之间，前面人少的排在前面，比如[7,0], [7,1]排在最前面所有人前面，这之后再插进来的人身高一定小于7，不论这个人插在数组的任何地方，都不会改变身高为7的数组中第二位数字，同时又能保证新插入的元素所在的位置是正确的。
实现代码：
public int[][] reconstructQueue(int[][] people) {
// 排序数组
Arrays.sort(people,
(a,b)->a[0]==b[0]?a[1]-b[1]:b[0]-a[0]);
// 新建一个List
List<int[]> list = new ArrayList<>();
// 将每个数组中第二个数值作为下标，将该数组插入List
for(int[] p : people){
list.add(p[1],p);
}
// 将list转为数组返回
int[][] res = new int[people.length][2];
for(int i=0;i<list.size();i++){
res[i]=list.get(i);
}
return res;
} 本题解法执行时间为6ms。
Runtime: 6 ms, faster than 81.09% of Java online submissions for Queue Reconstruction by Height.
Memory Usage: 42.7 MB, less than 87.23% of Java online submissions for Queue Reconstruction by Height.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-406-queue-reconstruction-by-height-解题思路分析/
View Comments (0)