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,毛想想好像对,有简单的数学证明吗?
|
|