美文网首页
[LeetCode] Queue Reconstruction

[LeetCode] Queue Reconstruction

作者: 阳丶小光 | 来源:发表于2019-06-14 19:09 被阅读0次

    Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

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

    Example
    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]]

    对于[i,j]按照i升序,j降序排序,然后按照j依次插入队列。
    矮个子对高个子没有影响。

    代码:

    class Solution {
        public int[][] reconstructQueue(int[][] people) {
            if (people.length == 0) {
                return people;
            }
            List<int[]> l = new ArrayList<>();
            Arrays.sort(people, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]);
            for (int i = 0; i < people.length; i++) {
                l.add(people[i][1], people[i]);
            }
            int[][] result = new int[people.length][people[0].length];
            for (int i = 0; i < l.size(); i++) {
                result[i] = l.get(i);
            }
            return result;
        }
    }
    

    相关文章

      网友评论

          本文标题:[LeetCode] Queue Reconstruction

          本文链接:https://www.haomeiwen.com/subject/jxopfctx.html