LEETCODE 406. Queue Reconstruction by Height 解题思路分析

题目大意：

根据身高重建队列

假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(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-解题思路分析/