T*****8
发帖数: 119 | 1 不知道有没有O(n)的算法。。。
Count smaller elements on right side
eg : [4,12,5,6,1,34,3,2]
o/p [3,5,3,3,0,2,1,0] | r*****b
发帖数: 310 | 2 As far as I know, we can have an O(nlogn) algo for this.
http://basicalgos.blogspot.com/2012/03/20-count-smaller-element
Not sure about O(n). I don't think that we can finally reach O(n).
【在 T*****8 的大作中提到】
: 不知道有没有O(n)的算法。。。
: Count smaller elements on right side
: eg : [4,12,5,6,1,34,3,2]
: o/p [3,5,3,3,0,2,1,0]
| l***i
发帖数: 1309 | 3 divide and conquer, count each half and also sort them, then you can do O(
nlogn). I agree that O(n) seems unlikely. | w***y
发帖数: 6251 | | t*********7
发帖数: 255 | 5 用O(N)空间,COUNT SORT做前面COUNT那个PROCESS,出来的数组就是这个数字之前有几个
比他小的吧...这样行么? | q******8
发帖数: 848 | 6 nlogn吧，sort，然后binary search找。 | P*******U
发帖数: 203 | 7 binary search 的时候怎么做到只考虑右边的比它小的？
【在 q******8 的大作中提到】
: nlogn吧，sort，然后binary search找。
| e***l
发帖数: 710 | 8 从后往前建堆. 记录新node移动的信息. 整个复杂度应该是build heap的时间，O(n)。
这样对不对？ | c***g
发帖数: 472 | 9 应该是，BINARY SEARCH之后，就可以找到INDEX，这个INDEX就是小于它的个数吧
er) 的大作中提到: 】
【在 P*******U 的大作中提到】
: binary search 的时候怎么做到只考虑右边的比它小的？
| P*******U
发帖数: 203 | 10 是啊，但是题目要求Count smaller elements on right side，不是general的smaller
elements啊
【在 c***g 的大作中提到】
: 应该是，BINARY SEARCH之后，就可以找到INDEX，这个INDEX就是小于它的个数吧
:
: er) 的大作中提到: 】
| | | s******n
发帖数: 3946 | 11 维护一个bst，每个节点存子树的节点总数。
来一个数字后插入，旋转等，需要修改节点数。。
那么比这个数字小的节点总数为：
插入节点的左儿子节点数，加上所有祖先节点的左儿子节点数，向上查找祖先节点的终止条件是当前节点已经是父亲节点的左儿子。 | e***l
发帖数: 710 | 12 从答案[3,5,3,3,0,2,1,0]推不出来排序的结果，所以先sort的话做了多余的操作。从
后往前建堆，虽然是n次lgn的binary search，但是这个级数能收敛到O(n)。你看书上
建堆的分析。这样应该是对的。 | s******n
发帖数: 3946 | 13 把一个数字插入堆中，如何知道堆中比这个数字小的集合总数？堆的特性是某一节点的
后代都比它小，但不代表所有比它小的都是它后代。
【在 e***l 的大作中提到】
: 从后往前建堆. 记录新node移动的信息. 整个复杂度应该是build heap的时间，O(n)。
: 这样对不对？
| e***l
发帖数: 710 | 14 你说的对。我再想想
【在 s******n 的大作中提到】
: 把一个数字插入堆中，如何知道堆中比这个数字小的集合总数？堆的特性是某一节点的
: 后代都比它小，但不代表所有比它小的都是它后代。
| q******8
发帖数: 848 | 15 int[] smaller_on_right(int[] array){
int length = array.length;
int[] result = new int[length];
ArrayList arraylist = new ArrayList();
for(int i=0; i
arraylist.add(array[i]);
}
Collections.sort(arraylist);//nlgn
for(int j=0; j
result[j] = Collections.binarySearch(arraylist, array[j]);//lgn
arraylist.remove(result[j]);//这步如果是array的话，算法就不是
nlogn了，不过如果是linkedlist的话，可以在每个node里存个index，remove就是o（1
）了
}
return result;
} | w****o
发帖数: 2260 | 16 数组里可以有重复的数吗？
如果a[] = { 5 5 5 5 5}, 结果是[ 0 0 0 0 0]吗?
【在 T*****8 的大作中提到】
: 不知道有没有O(n)的算法。。。
: Count smaller elements on right side
: eg : [4,12,5,6,1,34,3,2]
: o/p [3,5,3,3,0,2,1,0]
| T*****8
发帖数: 119 | 17 不知道有没有O(n)的算法。。。
Count smaller elements on right side
eg : [4,12,5,6,1,34,3,2]
o/p [3,5,3,3,0,2,1,0] | r*****b
发帖数: 310 | 18 As far as I know, we can have an O(nlogn) algo for this.
http://basicalgos.blogspot.com/2012/03/20-count-smaller-element
Not sure about O(n). I don't think that we can finally reach O(n).
【在 T*****8 的大作中提到】
: 不知道有没有O(n)的算法。。。
: Count smaller elements on right side
: eg : [4,12,5,6,1,34,3,2]
: o/p [3,5,3,3,0,2,1,0]
| l***i
发帖数: 1309 | 19 divide and conquer, count each half and also sort them, then you can do O(
nlogn). I agree that O(n) seems unlikely. | w***y
发帖数: 6251 | | | | t*********7
发帖数: 255 | 21 用O(N)空间,COUNT SORT做前面COUNT那个PROCESS,出来的数组就是这个数字之前有几个
比他小的吧...这样行么? | q******8
发帖数: 848 | 22 nlogn吧，sort，然后binary search找。 | P*******U
发帖数: 203 | 23 binary search 的时候怎么做到只考虑右边的比它小的？
【在 q******8 的大作中提到】
: nlogn吧，sort，然后binary search找。
| e***l
发帖数: 710 | 24 从后往前建堆. 记录新node移动的信息. 整个复杂度应该是build heap的时间，O(n)。
这样对不对？ | c***g
发帖数: 472 | 25 应该是，BINARY SEARCH之后，就可以找到INDEX，这个INDEX就是小于它的个数吧
er) 的大作中提到: 】
【在 P*******U 的大作中提到】
: binary search 的时候怎么做到只考虑右边的比它小的？
| P*******U
发帖数: 203 | 26 是啊，但是题目要求Count smaller elements on right side，不是general的smaller
elements啊
【在 c***g 的大作中提到】
: 应该是，BINARY SEARCH之后，就可以找到INDEX，这个INDEX就是小于它的个数吧
:
: er) 的大作中提到: 】
| s******n
发帖数: 3946 | 27 维护一个bst，每个节点存子树的节点总数。
来一个数字后插入，旋转等，需要修改节点数。。
那么比这个数字小的节点总数为：
插入节点的左儿子节点数，加上所有祖先节点的左儿子节点数，向上查找祖先节点的终止条件是当前节点已经是父亲节点的左儿子。 | e***l
发帖数: 710 | 28 从答案[3,5,3,3,0,2,1,0]推不出来排序的结果，所以先sort的话做了多余的操作。从
后往前建堆，虽然是n次lgn的binary search，但是这个级数能收敛到O(n)。你看书上
建堆的分析。这样应该是对的。 | s******n
发帖数: 3946 | 29 把一个数字插入堆中，如何知道堆中比这个数字小的集合总数？堆的特性是某一节点的
后代都比它小，但不代表所有比它小的都是它后代。
【在 e***l 的大作中提到】
: 从后往前建堆. 记录新node移动的信息. 整个复杂度应该是build heap的时间，O(n)。
: 这样对不对？
| e***l
发帖数: 710 | 30 你说的对。我再想想
【在 s******n 的大作中提到】
: 把一个数字插入堆中，如何知道堆中比这个数字小的集合总数？堆的特性是某一节点的
: 后代都比它小，但不代表所有比它小的都是它后代。
| | | q******8
发帖数: 848 | 31 int[] smaller_on_right(int[] array){
int length = array.length;
int[] result = new int[length];
ArrayList arraylist = new ArrayList();
for(int i=0; i
arraylist.add(array[i]);
}
Collections.sort(arraylist);//nlgn
for(int j=0; j
result[j] = Collections.binarySearch(arraylist, array[j]);//lgn
arraylist.remove(result[j]);//这步如果是array的话，算法就不是
nlogn了，不过如果是linkedlist的话，可以在每个node里存个index，remove就是o（1
）了
}
return result;
} | w****o
发帖数: 2260 | 32 数组里可以有重复的数吗？
如果a[] = { 5 5 5 5 5}, 结果是[ 0 0 0 0 0]吗?
【在 T*****8 的大作中提到】
: 不知道有没有O(n)的算法。。。
: Count smaller elements on right side
: eg : [4,12,5,6,1,34,3,2]
: o/p [3,5,3,3,0,2,1,0]
| h*********e
发帖数: 247 | 33 [5 4 3]
5 has 4 and 3 less than it, so 2 numbers to 5's right less than 5
4 has 3 less than it, so the result is
[2 1 0]
【在 w***y 的大作中提到】
: 55555 我怎么没看懂这个题目什么意思
|
|
