QueueReconstructionByHeight [source code]
public class QueueReconstructionByHeight {
static
/******************************************************************************/
public class Solution {
public int[][] reconstructQueue(int[][] people) {
if (people.length == 0) return new int[0][2];
Arrays.sort(people, new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
if (a[0] != b[0]) return b[0] - a[0];
else return a[1] - b[1];
}
});
Node res = new Node(people[0]);
for (int i = 1; i < people.length; i++)
res = insert(res, people[i]);
int[][] resAr = new int[people.length][2];
for (int i = 0; i < people.length; i++, res = res.next)
resAr[i] = res.person;
return resAr;
}
public Node insert(Node node, int[] person) {
Node newNode = new Node(person);
int rank = person[1], height = person[0];
if (rank == 0) {
newNode.next = node;
return newNode;
}
Node curr = node;
while (rank > 1) {
curr = curr.next;
rank--;
}
Node next = curr.next;
newNode.next = next;
curr.next = newNode;
return node;
}
public static class Node {
int[] person;
Node next;
public Node(int[] p) {
person = p;
}
}
}
/******************************************************************************/
public static void main(String[] args) {
QueueReconstructionByHeight.Solution tester = new QueueReconstructionByHeight.Solution();
int[][][] inputs = {
{{7,0}, {4,4}, {7,1}, {5,0}, {6,1}, {5,2}}, {{5,0}, {7,0}, {5,2}, {6,1}, {4,4}, {7,1}},
{}, {},
};
for (int i = 0; i < inputs.length / 2; i++) {
int[][] nums = inputs[2 * i];
String input = Matrix.printMatrix(nums);
String output = Matrix.printMatrix(tester.reconstructQueue(nums));
String expected = Matrix.printMatrix(inputs[1 + 2 * i]);
System.out.println(Printer.separator ());
System.out.println(Printer.wrapColor(input, "magenta") + " -> " + output + Printer.wrapColor(", expected: " + expected, output.equals(expected) ? "green" : "red"));
}
}
}
这个题目刚拿到手的时候一丁点儿的思路都没有, 别提其实还看到了提示的tag是greedy, 还是不会做;
后来想了半天, 终于有了一点思路; 这里我有一个担忧, 真正面试的时候不知道tag, 万一想不到greedy怎么办? 当然可以指望面试官给你一个hint, 不过万一碰到不肯给hint的呢?
至于这个思路本身是怎么得到的, 只能说算法问题本身, 最后拿到一个例子想算法的第一步, 最好的还是考虑, how would a human do it? or how would you do it? 只有当你自己知道怎么完成这个要求以后, 你才能教会电脑怎么去做;
或许拿到一个题目的时候, 一个统一的思路是可以先考虑这个题目可以符合的集中可能的tag? 加上之前我们讨论过, 应该给每一个tag总结一个常用套路大全, 这样我在解题没有思路的时候至少有一个fallback的search tree.
用什么数据结构来保存the list in construction: 我最后决定还是用LinkedList, 而且是自己做的node, 因为Std的那些其实感觉都是一个类似array的存在, 不适合我想要达到的这个在mutation上高度灵活的要求.
insert的返回值应该是什么: 刚开始认为是void, 后来想到应该是node, 因为insert的时候整个list的head可能会变化, 这样res 指向的就未必是大head了. 所以每次insert把大head都返回, 这样就可以保证始终have access to the big head;
一步一步来, 每一步该处理的问题(该做出的决定)一定要处理完整, 或者至少脑子里buffer起来. 因为很多时候做到下一步感觉逻辑无从下手就是因为上一步有遗留问题/决定没有理清. 比如这里这个comparator, 最后一个bug就是因为compare的第二步写反了. 你刚开始写的时候是可以先随便写一个, 当做是默认值一样, 不出问题不改. 但是你脑子里对于这个决定要buffer起来, 后面当真出问题的时候, 要知道可能是你哪里的细节没有处理到位.
一个一个数iteration的时候, 各个var考虑的值最好的还是at the beginning of each iteration的时刻的; 这样方便思考每个var的边界取值, 尤其是var的哪些取值满足循环header的yes-condition.
最后的速度是19ms (72%), 还算可以接受吧. 这个题目写的真的是很艰难的, 第一次感受到了middle题的威力, 考察很多的知识点. 不过感觉这个问题是不是还是想复杂了?
这个是submission最优解: 15(98):
public class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
int k = Integer.compare(b[0], a[0]);
return k != 0? k : Integer.compare(a[1], b[1]);
}
});
List<int[]> res = new ArrayList<>();
for(int[] p: people) {
res.add(p[1], p);
}
return res.toArray(new int[people.length][]);
}
}
可以看到, 非常的精简, 还很快. 他的sort跟我是一样的做的, 不过他sort之后好像看到了什么我没有看到的本质: 直接让rank作为一个person的index就行了; 卧槽trace画了一下居然是对的.
有点看不懂;
这个代码是NlgN的时间, 我的其实是N^2, 因为要traverse list;
这个是作者的解释:
- Pick out tallest group of people and sort them in a subarray (S). Since there's no other groups of people taller than them, therefore each guy's index will be just as same as his k value.
- For 2nd tallest group (and the rest), insert each one of them into (S) by k value. So on and so forth.
他们说其实这个算法也做不到NlgN:
What is the time complexity?
O(nlgn) + O(n * n) = O(n^2) ? because arraylist add is O(n)
感觉是对的, 这个代码的其实应该也是O(N^2);
另外我还是认为我自己的这个版本是值得学习的. 我这个版本其实就是一个很基本功的东西: 学会怎样把自己脑子里how I solve it as a human的heuristic转换成为算法直接得到的结果. 这样一个转化能力在面试过程中更容易让我受益. 以及一开始通过一个例子的操作, 来想到这个sort, 我也认为很有教育意义;
唯一要想到什么教训的话, 就是感觉这个insert其实我写的还是不够熟练, 当时写的时候, 尤其是变量更新这一块, 写的还是有点磕磕巴巴. 希望后面通过大量的训练, 能够做到像这种特别基础的操作的函数(当然是在当前问题的context下, 所以并不是说要你背代码)非常迅速的写出来, 别你妈这么简单一个东西写半天. 我这个算法只要我能够做到快速写完insert, 实际上最后虽然我的代码长, 但是写代码花的时间未必很久;
这个是stefan对于这个算法的理解:
I didn't come up with that myself, but here's my own explanation of it, as I haven't seen anybody explain it (and was asked to explain it):
People are only counting (in their k-value) taller or equal-height others standing in front of them. So a smallest person is completely irrelevant for all taller ones. And of all smallest people, the one standing most in the back is even completely irrelevant for everybody else. Nobody is counting that person. So we can first arrange everybody else, ignoring that one person. And then just insert that person appropriately. Now note that while this person is irrelevant for everybody else, everybody else is relevant for this person - this person counts exactly everybody in front of them. So their count-value tells you exactly the index they must be standing.
So you can first solve the sub-problem with all but that one person and then just insert that person appropriately. And you can solve that sub-problem the same way, first solving the sub-sub-problem with all but the last-smallest person of the subproblem. And so on. The base case is when you have the sub-...-sub-problem of zero people. You're then inserting the people in the reverse order, i.e., that overall last-smallest person in the very end and thus the first-tallest person in the very beginning. That's what the above solution does, Sorting the people from the first-tallest to the last-smallest, and inserting them one by one as appropriate.
他这个理解非常的聪明, 其实是用recursion的观点来理解: 他的解释是一个top-down的下行的过程,然后实际的代码的那个insert, 实际上就是一个上行的过程, 就有点类似DP的问题上面, 可以用top-down的思路来写代码, 也可以用bottom-up的思路来写代码;
事实上仔细想想这个insert的代码, 确实是这样的! 当我insert ith 人的时候, 我是不用管前面的人是怎么insert的, 我要the result(subsolution) of the previous (tallest) i - 1 people already inserted就行了; 然后我拿着这个subsolution, 我只要考虑我当前的ith需要干什么就行了, 这个完全就是DP的思路;
只能说这个代码的原作者对于recursion/DP真的是理解的出神入化了;
这个是另外一个人给出的解释, 也很好:
We first sort the people to make them stand from the highest to shortest. For people with same height, sort them according to the count of people before them from small to big.
Then, we use the way similar to insert sorting to reorder the people. For a given person to insert, all the people already sorted are higher, so we just insert him in the "right" place to make the people before him as his "count" indicates. Since he is shorter than all the people in the sorted list, the "count" of the "existing" people does not be broken by the insertion.
public int[][] reconstructQueue(int[][] people) {
if (people == null || people.length == 0 || people[0].length == 0)
return new int[0][0];
Arrays.sort(people, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
if (b[0] == a[0]) return a[1] - b[1];
return b[0] - a[0];
}
});
int n = people.length;
ArrayList<int[]> tmp = new ArrayList<>();
for (int i = 0; i < n; i++)
tmp.add(people[i][1], new int[]{people[i][0], people[i][1]});
int[][] res = new int[people.length][2];
int i = 0;
for (int[] k : tmp) {
res[i][0] = k[0];
res[i++][1] = k[1];
}
return res;
}
这个想法更接近于我自己写代码的时候思考的方式, 用invariant的方式来思考. 不过最后想法上还是差了一口气;
stefan也同意上面这个算法虽然很厉害, 但是实际上是N^2. 他自己改进到了NlgN, 代码是Python的, 所以我就没有看了: https://discuss.leetcode.com/topic/60550/o-n-sqrt-n-solution/13;
另外G4G上面好像有一个对于这个技术的介绍: http://www.geeksforgeeks.org/sqrt-square-root-decomposition-technique-set-1-introduction/
这个有空回去看一下;
discussion好像还有一个思路类似我的, 但是加速了的算法: https://discuss.leetcode.com/topic/60422/worse-case-o-n-2-and-o-nlogn-in-average-using-binary-tree-travel
我的算法是build一个LinkedList, 他的算法是build一个类似BST的, 最后一个InOrder收集一下结果就行了. 这种技巧暂时就懒得看了, 加上又是Python;
有人认为这个题目, LinkedList比ArrayList要好: https://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist
但是stefan在底下反驳认为这个观点完全不对, 而且OJ最后的结果也proved the countrary: 这个是帖子: https://discuss.leetcode.com/topic/60437/java-solution-using-priorityqueue-and-linkedlist/5
for linklist, it take O(n) to get to position;
for arraylist, it take O(n) to move elements after position to the back.(seems like there is a super fast system call to do this)
这个是discussion里面另外一个直接用array来collect的做法:
We always choose the current shortest height (so we need to sort input first), and then try to put it into the right position. We simply scan from the left and count how many persons are really >= its own height. Then we put the person into the empty slot.
public class Solution {
public int[][] reconstructQueue(int[][] people) {
if (people == null || people.length <= 1) {
return people;
}
Arrays.sort(people, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0];
}
});
int n = people.length;
int[][] ret = new int[n][];
for (int i = 0; i < n; i++) {
for (int j = 0, ahead = 0; j < n; j++) {
if (ahead < people[i][1]) {
ahead += (ret[j] == null || ret[j][0] >= people[i][0]) ? 1 : 0;
} else if (ret[j] == null) {
ret[j] = people[i];
break;
}
}
}
return ret;
}
}
打印了trace也不是很理解他这个算法, 他这个sort就跟别的算法的sort做的不一样; 他这个是先根据height ascending, 然后根据rank ascending;
看了一下trace, 大概的意思好像就是, 比如他从height最小的这个开始, 这个的位置肯定就在它rank的位置, 因为所有其他的person都比他高.
然后下一个人来了,这个人就不不考虑上一个人因为上一个人比自己矮. 大体思路好像是这样; 具体代码懒得看了, 贴个代码一点变量说明都没有这帮人也是烦;
这里这个双循环, 一个i是用来iterate people的, 一个j是用来iterate ret的. 手上拿着people[i]就从左往右挨个比较; ahead代表走过的j的长度里面, 有多少是实际可以count到people[i]的rank里面去的; 你看他ahead更新的方式(ahead += 0 if !(ret[j] == null || ret[j][0] >= people[i][0]), which is (ret[j] != null && ret[j][0] < people[i][o]])) : 如果当前的ret[j]已经放了一个人, 而且这个人height小于我们to be placed的people[i], 那么这个位置(以及这个位置上的人就不被计算到people[i]的rank里面去);
这个是我在下面回复的解释:
To relieve the pain for future readers:
this solution sort in the manner of height ascending first, and rank ascending if height tie (rank as defined as number of people taller than or equal to my height who is also standing before me).
After sorting, we iterate through people, for each people[i], we try to directly put it into the correct position. j is used to iterate from left to right in the output list, while ahead is used to record the actual number of slots that could be counted into the calculation of people[i]'s rank. If at position j we already have somebody placed, and also this somebody is shorter than people[i] (which is yet to be placed in this iteration of the outer loop), then we don't count this slot into ahead since people[i]'s rank's calculation does not take this slot's person into account anyway(he's shorter).
When ahead reaches people[i]'s rank, put him there.
Come on people, at least tell the readers what your variable name means.
Problem 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]]
Difficulty:Medium
Total Accepted:25.4K
Total Submissions:45.8K
Contributor: LeetCode
Companies
google
Related Topics
greedy
Similar Questions
Count of Smaller Numbers After Self