N*****8
发帖数: 253 | 1 1. 这个算是老题了，就是给一个unsorted array算每个element有多少在右边等于或小
于自己的elements，比如:
input array = {1,3,2,4,5,4,2}
output array = {0,2,1,2,2,1,0}
比较常规的建树解法需要O(nlogn)时间+O(n)空间，有没有O(n)的时间解法，空间不限？
2. 算n个array的median | p*****2
发帖数: 21240 | 2
限？
input array = {1,3,2,4,5,4,2}
output array = {0,2,1,2,2,1,0}
这个没看明白。
【在 N*****8 的大作中提到】
: 1. 这个算是老题了，就是给一个unsorted array算每个element有多少在右边等于或小
: 于自己的elements，比如:
: input array = {1,3,2,4,5,4,2}
: output array = {0,2,1,2,2,1,0}
: 比较常规的建树解法需要O(nlogn)时间+O(n)空间，有没有O(n)的时间解法，空间不限？
: 2. 算n个array的median
| N*****8
发帖数: 253 | 3 呵呵，二爷我还以为你肯定见过这题呢。
就是a[i]算一共有多少比自己小或等于的elements在a[i+1:n-1]的区间。
【在 p*****2 的大作中提到】
:
: 限？
: input array = {1,3,2,4,5,4,2}
: output array = {0,2,1,2,2,1,0}
: 这个没看明白。
| p*****2
发帖数: 21240 | 4
不好意思。刚才晕了。去算大于或等于的了。这题没见过呀。我其实做题很少的。
【在 N*****8 的大作中提到】
: 呵呵，二爷我还以为你肯定见过这题呢。
: 就是a[i]算一共有多少比自己小或等于的elements在a[i+1:n-1]的区间。
| N*****8
发帖数: 253 | 5 版本有贴过这题，但是原帖中没有O(n)的解法。但是还是好奇，到底有没有O(n)的解法。
还有一道相似题就是inversion count了，就是给个array算在右边比自己大的元素个数
。就是mergesort的变形了，但是好像也没有O(n)的解法，同样空间不限。
【在 p*****2 的大作中提到】
:
: 不好意思。刚才晕了。去算大于或等于的了。这题没见过呀。我其实做题很少的。
| l*********8
发帖数: 4642 | 6 第一个题目， 如果有general 的O(n)的时间解法,那么就代表有general的O(n)时间排
序算法了。 所以我觉得在一般情况下， 没有O(n)的时间解法。
限？
【在 N*****8 的大作中提到】
: 1. 这个算是老题了，就是给一个unsorted array算每个element有多少在右边等于或小
: 于自己的elements，比如:
: input array = {1,3,2,4,5,4,2}
: output array = {0,2,1,2,2,1,0}
: 比较常规的建树解法需要O(nlogn)时间+O(n)空间，有没有O(n)的时间解法，空间不限？
: 2. 算n个array的median
| t*********7
发帖数: 255 | 7 第一题应该没有O(n)的搞法吧...第二题倒是有O(n)的搞法,好像是一篇高端论文...
nlgn的搞法应该是median of medians algo...同求熟悉这个算法的大神指点. | p*****2
发帖数: 21240 | 8 第一题nlogn的解法就是先建一个BST， 然后再从后往前走一遍。每到一个element，就
search一下BST,然后大于等于他的node都＋1, 然后看他自己的node的counter是多少就
行了？ | l*********8
发帖数: 4642 | 9 我觉得可以在BST的每个node里面存上子树的节点总数
【在 p*****2 的大作中提到】
: 第一题nlogn的解法就是先建一个BST， 然后再从后往前走一遍。每到一个element，就
: search一下BST,然后大于等于他的node都＋1, 然后看他自己的node的counter是多少就
: 行了？
| p*****2
发帖数: 21240 | 10
就是这个意思。但是一次都存不行吧？还是得按照从右往左的顺序吧？
或者用最后一个element做root，但是不能保证balanced。
【在 l*********8 的大作中提到】
: 我觉得可以在BST的每个node里面存上子树的节点总数
| | | l*********8
发帖数: 4642 | 11 从root到destination node的path上的所有节点的右子树的node count加起来，应该可
以吧？
【在 p*****2 的大作中提到】
:
: 就是这个意思。但是一次都存不行吧？还是得按照从右往左的顺序吧？
: 或者用最后一个element做root，但是不能保证balanced。
| N*****8
发帖数: 253 | 12 从右往左扫数组，然后建AVL/RB tree(普通的BST不能保证logn时间)，右边的分支需要
把root的个数加上然后加一，左边的不需要。
然后再扫数组，从左往右，每次node都减一。
【在 p*****2 的大作中提到】
: 第一题nlogn的解法就是先建一个BST， 然后再从后往前走一遍。每到一个element，就
: search一下BST,然后大于等于他的node都＋1, 然后看他自己的node的counter是多少就
: 行了？
| N*****8
发帖数: 253 | 13 嗯，你的说法有道理。
【在 l*********8 的大作中提到】
: 第一个题目， 如果有general 的O(n)的时间解法,那么就代表有general的O(n)时间排
: 序算法了。 所以我觉得在一般情况下， 没有O(n)的时间解法。
:
: 限？
| N*****8
发帖数: 253 | 14 先求n个array自己的median，然后再在这个n个median中求median，这个median就是整
个n个数组的median，毛想想好像对，有简单的数学证明吗？
【在 t*********7 的大作中提到】
: 第一题应该没有O(n)的搞法吧...第二题倒是有O(n)的搞法,好像是一篇高端论文...
: nlgn的搞法应该是median of medians algo...同求熟悉这个算法的大神指点.
| p*****2
发帖数: 21240 | 15
是这样。我的意思是面试写的时候应该怎么建tree呢？
【在 l*********8 的大作中提到】
: 从root到destination node的path上的所有节点的右子树的node count加起来，应该可
: 以吧？
| N*****8
发帖数: 253 | 16 可能更多的是讲思路吧，顺便把AVL/RB里面的关键算法也考了，突然觉得这个题一举两
得啊。 | c*******r
发帖数: 610 | | r********g
发帖数: 1351 | 18 这个不对吧。。例子：
1 2 100
3 4 50
median应该是3.5啊
【在 N*****8 的大作中提到】
: 先求n个array自己的median，然后再在这个n个median中求median，这个median就是整
: 个n个数组的median，毛想想好像对，有简单的数学证明吗？
| h*****f
发帖数: 248 | 19 BST不一定能在为O(n)内建成，因为可能要重新balance.
TopCoder的讨论中提到用merge sort. 应该可以ensure为O(nlogn) with O(n) space. | h*****f
发帖数: 248 | 20 Counter example:
1 2 3=>median 2
4 5 6=>median 5
1 5 5=>median 5
median of 2 5 5 = 5
actual median of all 3 arrays = 4
【在 N*****8 的大作中提到】
: 先求n个array自己的median，然后再在这个n个median中求median，这个median就是整
: 个n个数组的median，毛想想好像对，有简单的数学证明吗？
|
|
