Leetcode 406. Queue Reconstruction by Height

Description

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

Solution

题意大致是一个人可以用一对整数(h, k)来描述,h代表人的高度,k代表左边比这个人高的人的个数。现随意给出了一个序列,让我们根据h, k进行排列。

题目的难点在于如何用代码描述整个排序过程:

  • 排序的规律是什么?
  • 用什么数据结构来一个个插入数据?

能解决上面的这两个问题,题目就解决了。

其实排序的规律分两步:1. 先将高度降序排序,2. 高度相等的按照k升序排序。然后按照k一个个插入到最终的数据结构中。在本题中选用的数据结构是LinkedList。因为它的插入时间复杂度是O(1)。

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (p1, p2) -> p1[0] == p2[0] ? p1[1] - p2[1] : p2[0] - p1[0]);
        LinkedList<int[]> res = new LinkedList<>();
        for (int[] p : people) {
            res.add(p[1], p);
        }
        return res.toArray(new int[people.length][2]);
    }
}

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

浙ICP备19002997号