Leetcode刷题java之406. 根据身高重建队列(一天一道编程题之第五天)

红太狼 2023-07-08 06:00 6阅读 0赞

执行结果：

通过

显示详情

执行用时 :11 ms, 在所有 Java 提交中击败了48.48% 的用户

内存消耗 :42 MB, 在所有 Java 提交中击败了79.66%的用户

题目：

假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(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\]\]

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/queue-reconstruction-by-height  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

个子矮的相对于个子高的是看不见的，所以先排个子高的，来模拟一下这个过程。

算法就是先排序，从大到小排序，如果值相同，那么就按第二列从小到达排序。

然后进行排列，第二列就是它要插入的索引。

参考leetcode题解：[https://leetcode-cn.com/problems/queue-reconstruction-by-height/solution/gen-ju-shen-gao-zhong-jian-dui-lie-by-leetcode/][https_leetcode-cn.com_problems_queue-reconstruction-by-height_solution_gen-ju-shen-gao-zhong-jian-dui-lie-by-leetcode]

代码：

class Solution {
        public int[][] reconstructQueue(int[][] people) {
            //按照第一列从大到小排序，如果第一列的值相同的话，就比较第二列，第二列小的放前面
            Arrays.sort(people,new Comparator<int[]>()
            {
                public int compare(int[] o1,int[] o2)
                {
                    return o1[0]==o2[0]?o1[1]-o2[1]:o2[0]-o1[0];
                }
            });
            //定义一个list，可以进行插入操作，在相应的索引位置插入
            List<int[]> result=new ArrayList<>();
            for(int[] p:people)
            {
                result.add(p[1],p);
            }
            return result.toArray(new int[people.length][2]);
        }
    }

[https_leetcode-cn.com_problems_queue-reconstruction-by-height_solution_gen-ju-shen-gao-zhong-jian-dui-lie-by-leetcode]: https://leetcode-cn.com/problems/queue-reconstruction-by-height/solution/gen-ju-shen-gao-zhong-jian-dui-lie-by-leetcode/