X

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-解题思路分析/
Categories: leetcode
kwantong:

View Comments (0)