406. Queue Reconstruction by Height

Posted on | In |

LeetCode 406. Queue Reconstruction by Height

根据题意，输入的类型是int[][]，其中int[i][0]表示第i个元素的高度，int[i][1]表示第i个元素前面大于等于这个元素高度的元素的个数。

考虑数组中只包含高度相同的元素的情况。我们可以根据元素的第二个分量正序排序，得出正确结果。

例如：

输入为int[][] s = { {7, 1}, {7, 2}, {7, 0} }，我们只需要根据每个元素的第二分量排序，得到{ {7, 0}, {7, 1}, {7, 2} }即可。

考虑数组中包含高度不同的元素，也就是一般情况。我们可以根据元素的第一个分量先将所有元素逆序排序，如果第一个分量相同则按第二个分量正序排序。然后将所有元素插入结果中的第二分量表示的位置。

例如：

int[][] s = { {6, 1}, {7, 1}, {7, 0} }，排序后的结果应该是{ {7, 0}, {7, 1}, {6, 1} }。

将所有元素按顺序插入元素第二分量代表的位置后的结果是{ {7, 0}, {6, 1}, {7, 1} }。

代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
public int[][] reconstructQueue(int[][] people) {
    Arrays.sort(people, new Comparator<int[]>() {
        @Override public int compare(int[] p1, int[] p2) {
            return p1[0] == p2[0] ? Integer.compare(p1[1], p2[1]) : Integer.compare(p2[0], p1[0]);
        }
    });
    List<int[]> temp = new LinkedList<>();
    for (int i = 0; i < people.length; i++) {
        temp.add(people[i][1], people[i]);
    }
    return temp.toArray(new int[people.length][]);
}