首页 > 其他 > 详细

[LeetCode] 406. Queue Reconstruction by Height

时间:2020-06-07 10:33:48      阅读:26      评论:0      收藏: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]]

根据身高重建队列。题意是给一个二维数组[h, k],其中h表示每个人的身高,k表示在这个人之前有几个人的身高大于等于这个人。input的顺序是错的,请你根据每个人的[h, k]的状况对input进行正确排序。

思路是先按照h排序,如果h相同,则k小的在前。此时创建一个list,将排序后的结果加入list,加入的规则是将每个人的[h, k]加入到list的k位置上。

时间O(nlogn)

空间O(n^2) - output

Java实现

 1 class Solution {
 2     public int[][] reconstructQueue(int[][] people) {
 3         Arrays.sort(people, (a, b) -> a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);
 4         // 新建一个List
 5         List<int[]> list = new ArrayList<>();
 6         // 将每个数组中第二个数值作为下标,将该数组插入List
 7         for (int[] p : people) {
 8             list.add(p[1], p);
 9         }
10         // 将list转为数组返回
11         int[][] res = new int[people.length][2];
12         for (int i = 0; i < list.size(); i++) {
13             res[i] = list.get(i);
14         }
15         return res;
16     }
17 }

 

LeetCode 题目总结

[LeetCode] 406. Queue Reconstruction by Height

原文:https://www.cnblogs.com/cnoodle/p/13058320.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!