406. 根据身高重建队列

2020-04-17

LeetCode

贪心

3 分钟读完 (大约 494 个字) 0次访问

leetcode 406. 根据身高重建队列

题目：406. 根据身高重建队列

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

方法：贪心

思路：先按身高 h 降序、个数 k 值升序排列，然后将其按顺序插入到k的位置上，如果k位置上已有数据，则将原有数据后移一位再插入，由于之前排好了序，插入时会先插入身高较高的，所以后面如果k位置上有数据需要后移一位，对后移的数据也不会有影响，因为新插入的数据身高一定会比后移的低。

运行数据：执行用时：8 ms，内存消耗：40.8 MB

// LeetCode指定调用方法
public int[][] reconstructQueue(int[][] people) {
		
    // 判断输入数据是否为空，为空则返回空结果
    if (people == null || people.length == 0 || people[0].length == 0) {
        return new int[0][0];
    }

    // 身高 h 降序、个数 k 值升序排列
    Arrays.sort(people, new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            return o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0];
        }
    });

    // 插入到k的位置上，如果k位置上已有数据，则将原有数据后移一位再插入，此时使用list，它会自动后移数据
    List<int[]> list = new ArrayList<>();
    for (int[] p : people) {
        list.add(p[1], p);
    }

    // 将结果list转为数组结果返回
    return list.toArray(new int[list.size()][]);
}