GuilinDev

Lc0406

05 August 2008

406 Queue Reconstruction by Height

原题概述

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers 

1

(h, k)
, where 
1

h
is the height of the person and 
1

k
is the number of people in front of this person who have a height greater than or equal to 
1

h
. Write an algorithm to reconstruct the queue.

Note:
The number of people is less than 1,100.

Example

1
2
3
4
5

Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

题意和分析

给一个队列，里面的人用[h,k]二元组表示，h代表当前人的高度，k代表在这个人前面且高度大于等于它的h的人数，现在要求按照这个二元组重构这个队列使之变得有效。这道题的思路是(贪心算法)： (1)首先找到身高最高的人并对他们进行排序。 (2)然后找到身高次高的人，按照他们的前面的人数把他们插入到最高的人群中。 (3) 以此类推。

因此这是一个排序和插入的过程，按照身高进行降序排序，如果我们按照先处理身高最高的，那他们的k值就是他们所应该在的位置——因为已经没有比他们更高的了。 所以我们从高度从高到低按照k值的位置一直插入到答案中即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator<int[]>() {//按身高降序排序(h大的在前面)，按k的大小升序排列(k小的在前面)
            public int compare(int[] a, int[] b) {
                if (a[0] != b[0]) {
                    return -a[0] + b[0];//先排身高
                } else {
                    return a[1] - b[1];//身高一样再排前面的人数
                }
            }
        });

        List<int[]> result = new LinkedList<int[]>();//在结果中选择合适的位置插入存储结果
        for (int i = 0; i < people.length; i++) {
            int[] onePeople = people[i];
            result.add(onePeople[1], onePeople);
        }
        return result.toArray(new int[people.length][]);
    }
}
This site is open source. Improve this page.