[数据结构与算法]LeetCode-406-根据身高重建队列

LeetCode-406-根据身高重建队列

思路

这里使用插入排序法
首先对原来的数组进行一次排序，以身高为第一关键字进行降序排序，以人数为第二关键字进行升序排序。
然后进行插入排序即可。Java中的ArrayList的add(i,num)表示插入到第i个位置，原来的位置如果存在元素那么该元素自己和后面的元素就后移。
[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]
排序：
[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]
插入排序
[7,0]
[7,0],[7,1]
[7,0],[6,1],[7,1]
[5,0],[7,0],[6,1],[7,1]
[5,0],[7,0],[5,2],[6,1],[7,1]
[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]

代码

public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator<int[]>() {
            public int compare(int[] p1, int[] p2) {
                if (p1[0] != p2[0]) {
                    return p2[0] - p1[0];
                } else {
                    return p1[1] - p2[1];
                }
            }
        });
        List<int[]> ans = new ArrayList<int[]>();
        for (int[] person : people) {
            ans.add(person[1], person);
        }
        return ans.toArray(new int[ans.size()][]);
    }