首页 > 代码库 > LeetCode 406. Queue Reconstruction by Height

LeetCode 406. Queue Reconstruction by Height

转载请注明出处:http://www.cnblogs.com/liangyongrui/p/6351533.html 

 

贪心,具体见代码。

注释写的很详细。

 

public class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                //不同的时候按照第一维降序,相同的时候按照第二维升序
                return o1[0] != o2[0] ? -o1[0] + o2[0] : o1[1] - o2[1];
            }
        });
        //把排好序的数组插入链表中,根据第二维的下标插入即可,
        //因为排好序了,如果较小的元素插入的话,并不会影响最终的结果,
        //而前面已经插入的元素都是大于或等于将要插入的元素的,
        //所以直接按照第二维的下标插入是正确的。
        List<int[]> res = new LinkedList<>();
        for (int[] cur : people) {
            res.add(cur[1], cur);
        }
        return res.toArray(new int[people.length][]);
    }
}

 

LeetCode 406. Queue Reconstruction by Height