LeetCode 406.根据身高重建队列 | 解题思路及代码
2022/4/23 23:15:37
本文主要是介绍LeetCode 406.根据身高重建队列 | 解题思路及代码,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
根据身高重建队列
原题:406. Queue Reconstruction by Height
Problem Description
There are \(n\) people, we want them line up in the following way.
Given a two-dimensional array: \(people[n][2]\), where \(people[i]=[h_i][k_i]\), \(h_i\) means the height of \(i\)-th person, \(k_i\) means there are \(k_i\) people who are the same height as person \(i\) or taller than person \(i\) stand in front of person \(i\). So there are actually \(k_i\) or more people stand in front of person \(i\).
According to the two-dimentional array, line them up. It's promised that them can be lined up.
example
people =\([[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]\)
answer =\([[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]\)
Ideas
Firstly, let's consider a simpler case: people's height differs. No two people are the same height.
No same height
Assume there are a array \(line[n]\). We want to put everyone in this line. When we put \(people[i]=[h_i][k_i]\), assuming no one taller than him has been lined. We need to reserve \(k_i\) spaces in front of him for those \(k_i\) people who are higher than him. So we put person \(i\) at the \(k_i+1\)-th empty position.
How to ensure "no one taller than him has been lined"? That's sample, just put them in the line in ascending order of height.
Now we consider how to handle people who have same height.
Same height
For person \(i\), \(j\), we assume their height are the same. Without loss of generality, we assume \(k_i<k_j\)(if they are equal, they can't be lined as required).
Then we have: person \(i\) must stand in front of person \(j\). Otherwise it won't meet the requirement. The question now is should we put person \(i\) first or person \(j\) first.
If we put person \(i\) first. When puting person \(j\), we should put him at the \(k_j+1\)-th position as explained above. Those \(k_j+1\) empty space are reserve for people has
the same height or higher, but we have put person \(i\) who has the same height as \(j\) and \(i\) is in front of \(j\), alreadly taken a place himself! We should only reserve \(k_j\) empty space. So puting \(i\) first is not optimal.
If we put person \(j\) first. When puting \(i\), \(i\) is in front of \(j\) and that just take the place \(j\) left for \(i\). So that's established.
So we put people who has same height in \(k\) descending order.
Algorithm
Sort \(people\) array according to \(h_i\) as the first keyword in ascending order and \(k_i\) as the second keyword in descending order.
Put the sorted \(people[i]\) in the \(k_i+1\)-th position in turn.
The detailed code is as follows
public class p406 { public int[][] reconstructQueue(int[][] people) { int num = people.length; Arrays.sort(people, new Comparator<int[]>() { public int compare(int[] t1, int[] t2) { return t1[0] == t2[0] ? t2[1] - t1[1] : t1[0] - t2[0]; } }); int[][] ans = new int[num][]; for (int[] person : people) { int space = person[1] + 1; for (int i = 0; i < num; i++) { if (ans[i] == null) { space--; } if (space == 0) { ans[i] = person; break; } } } return ans; } }
Time&Space Complexity
Time complexity: \(O(\log n)\) for sort, \(O(n^2)\) for going through \(people\) array and find corresponding location for each person. So the total time complexity is \(O(n^2)\).
Space complexity: Sorting is implemented by recursive calls. So the time complexity is \(O(\log n)\).
这篇关于LeetCode 406.根据身高重建队列 | 解题思路及代码的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升