如果我们按照高度从高到低(如果高度相同的话，第二个数更小的人排前面)考虑所有的人，当我们处理排序后第i个人的时候，前面高度大于等于他的i - 1个人我们已经考虑过了，假设其要求前面高度大于等于他的人有k个，我们只需要将这个人在已经考虑过的所有人排在k + 1即可。因为后面的人只有两种情况：
- 高度和people[i]相等，但根据我们sort的规则，如果高度相同的话，第二个数更小的人排前面。所以其插入后也肯定排在people[i]后面。
- 高度小于people[i]，那么更不会影响people[i]排位的合理性。其前面仍然会有k个人比他高，这点不会变。
所以如果我们按照这个顺序考虑每个人people[i]，结束时每个人的顺位仍然是合理的。按照这个方法的话，其实就类似于insertion sort。时间复杂度O(n^2)，空间复杂度O(1)。代码如下：
另外一种方法会用到segment tree，关于segment tree的介绍可以参考这篇文章。那么我们要存什么，又查询什么呢？如果我们按照高度从低到高排序(如果高度相同的话，第二个数更大的人排前面)，我们从左到右依次考虑每一个人p = [i, j]，我们只需要把p插入到从左向右的第j + 1个available的slot即可，因为后面的人高度都是大于等于p的，而且前面的空着的j个slot都会填满，所以p最后会满足条件。所以对于长度为n的输入数组，segment tree要存的就是位于index i的slot是否被填上了。如果我们用1表示没填上，0表示填上，这虽然有点反直觉，但是我们如果找到第一个presum = j + 1的位置，并且没有被填上，这个就是p所要去的位置。所以segment tree的每个node存的是这个node所表示的区间[start, end]还有多少slot是available的，我们查询从左到右第k个available的slot的时候就运用binary search + presum即可。时间复杂度为O(n * log n)，空间复杂度O(n)，代码如下：
No comments:
Post a Comment