当前位置:网站首页>leetcode 406. Queue reconstruction by height
leetcode 406. Queue reconstruction by height
2022-07-01 12:00:00 【Blue feather birds】
You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). Each people[i] = [hi, ki] represents the ith person of height hi with exactly ki other people in front who have a height greater than or equal to hi.
Reconstruct and return the queue that is represented by the input array people. The returned queue should be formatted as an array queue, where queue[j] = [hj, kj] is the attributes of the jth person in the queue (queue[0] is the person at the front of the queue).
Example 1:
Input: people = [[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]]
Explanation:
Person 0 has height 5 with no other people taller or the same height in front.
Person 1 has height 7 with no other people taller or the same height in front.
Person 2 has height 5 with two persons taller or the same height in front, which is person 0 and 1.
Person 3 has height 6 with one person taller or the same height in front, which is person 1.
Person 4 has height 4 with four people taller or the same height in front, which are people 0, 1, 2, and 3.
Person 5 has height 7 with one person taller or the same height in front, which is person 1.
Hence [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] is the reconstructed queue.
Example 2:
Input: people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
Output: [[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]
people Each group in the array is [ height , There are several people who are taller than me or as tall as me ]
Press “ There are several people taller than me in front ” Order the array
Ideas :
First of all, make it clear , Suppose we have arranged the order now , Those who are taller than me in front 3 personal , Then adding a shorter one to the front will not affect the current order .
But adding a taller one in front of me will have an impact , The one higher than me in front is 4 Personal .
therefore , The first people According to height (people[i][0]) null , Make sure the high ones are lined up first , Then add the short one , Will not affect the order .
people[i] = [hi, ki], ki It means that there is ki Personal than the current i individual people high ,
Because it is arranged from high to low according to height , The existing ones in front are better than the current people high , So just put him insert To the first ki A place ,
Then the short one from behind insert It doesn't matter to go in front of him , No effect ki.
Understanding this is the key .
How do two people of the same height line up , It's the one in front (ki smaller ) Or the back (ki The larger )?
Just imagine , If the one behind first , such as (5,4): Height is 5 People who , There is 4 Someone taller than him or as tall as him ,
One more (5,2), want insert To the first 2 individual , stay (5,4) In front of , So good , There is another one as tall as him in front ,(5,4) Should become (5,5) 了 , Be affected by .
therefore , If you're the same height , First row ki smaller .
public int[][] reconstructQueue(int[][] people) {
int n = people.length;
Arrays.sort(people, (a, b)->(a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]));
List<int[]> res = new LinkedList<>();
for(int[] tmp : people) {
res.add(tmp[1], tmp);
}
return res.toArray(people);
}
边栏推荐
- 耐克如何常年霸榜第一名?最新財報答案來了
- 伸展树(一) - 概念和C实现
- Summary of JFrame knowledge points 2
- Custom grpc plug-in
- Uniapp uses uni upgrade Center
- Istio, ebpf and rsocket Broker: in depth study of service grid
- Seckill system 03 - redis cache and distributed lock
- Understanding of MVVM and MVC
- Wechat applet development - user authorization to log in to "suggestions collection"
- 用实际例子详细探究OpenCV的轮廓检测函数findContours(),彻底搞清每个参数、每种模式的真正作用与含义
猜你喜欢
研发效能度量框架解读
Learning summary on June 28, 2022
2022/6/28学习总结
Huawei HMS core joins hands with hypergraph to inject new momentum into 3D GIS
C summary of knowledge points 1
深入理解 grpc part1
【单片机】【数码管】数码管显示
Skip the test cases to be executed in the unittest framework
S7-1500PLC仿真
Y48. Chapter III kubernetes from introduction to mastery -- pod status and probe (21)
随机推荐
研发效能度量框架解读
redis常识
CPI tutorial - asynchronous interface creation and use
图的理论基础
Building external modules
redis中value/hush
Skip the test cases to be executed in the unittest framework
Redis startup and library entry
S7-1500plc simulation
证券账户销户后果 开户安全吗
Learning summary on June 30, 2022
Botu V15 add GSD file
内核同步机制
我在中山,到哪里开户比较好?实际上网上开户安全么?
Wechat applet development - user authorization to log in to "suggestions collection"
JS date format conversion method
[Maui] add click events for label, image and other controls
Chen Gong: Micro service, is it still so pure?
Talk about the pessimistic strategy that triggers full GC?
usb peripheral 驱动 - cable connect/disconnect