Redian新闻
>
EB1B,7封推荐信(5独立),3个中国人,会有问题吗?
avatar
EB1B,7封推荐信(5独立),3个中国人,会有问题吗?# Immigration - 落地生根
T*8
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]
avatar
b*k
2
5个独立的来自美国,英国,德国,意大利,新加坡。其中新加坡的是个中国人。两封
相关的都是中国人。
avatar
r*b
3
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]

avatar
H*e
4
我觉得没有问题。我记得有人有好几个中国的推荐人呢。
avatar
l*i
5
divide and conquer, count each half and also sort them, then you can do O(
nlogn). I agree that O(n) seems unlikely.
avatar
w*y
6
55555 我怎么没看懂这个题目什么意思
avatar
t*7
7
用O(N)空间,COUNT SORT做前面COUNT那个PROCESS,出来的数组就是这个数字之前有几个
比他小的吧...这样行么?
avatar
q*8
8
nlogn吧,sort,然后binary search找。
avatar
P*U
9
binary search 的时候怎么做到只考虑右边的比它小的?

【在 q******8 的大作中提到】
: nlogn吧,sort,然后binary search找。
avatar
e*l
10
从后往前建堆. 记录新node移动的信息. 整个复杂度应该是build heap的时间,O(n)。
这样对不对?
avatar
c*g
11
应该是,BINARY SEARCH之后,就可以找到INDEX,这个INDEX就是小于它的个数吧

er) 的大作中提到: 】

【在 P*******U 的大作中提到】
: binary search 的时候怎么做到只考虑右边的比它小的?
avatar
P*U
12
是啊,但是题目要求Count smaller elements on right side,不是general的smaller
elements啊

【在 c***g 的大作中提到】
: 应该是,BINARY SEARCH之后,就可以找到INDEX,这个INDEX就是小于它的个数吧
:
: er) 的大作中提到: 】

avatar
s*n
13
维护一个bst,每个节点存子树的节点总数。
来一个数字后插入,旋转等,需要修改节点数。。
那么比这个数字小的节点总数为:
插入节点的左儿子节点数,加上所有祖先节点的左儿子节点数,向上查找祖先节点的终止条件是当前节点已经是父亲节点的左儿子。
avatar
e*l
14
从答案[3,5,3,3,0,2,1,0]推不出来排序的结果,所以先sort的话做了多余的操作。从
后往前建堆,虽然是n次lgn的binary search,但是这个级数能收敛到O(n)。你看书上
建堆的分析。这样应该是对的。
avatar
s*n
15
把一个数字插入堆中,如何知道堆中比这个数字小的集合总数?堆的特性是某一节点的
后代都比它小,但不代表所有比它小的都是它后代。

【在 e***l 的大作中提到】
: 从后往前建堆. 记录新node移动的信息. 整个复杂度应该是build heap的时间,O(n)。
: 这样对不对?

avatar
e*l
16
你说的对。我再想想

【在 s******n 的大作中提到】
: 把一个数字插入堆中,如何知道堆中比这个数字小的集合总数?堆的特性是某一节点的
: 后代都比它小,但不代表所有比它小的都是它后代。

avatar
q*8
17
int[] smaller_on_right(int[] array){
int length = array.length;
int[] result = new int[length];
ArrayList arraylist = new ArrayList();
for(int i=0; iarraylist.add(array[i]);
}
Collections.sort(arraylist);//nlgn
for(int j=0; jresult[j] = Collections.binarySearch(arraylist, array[j]);//lgn
arraylist.remove(result[j]);//这步如果是array的话,算法就不是
nlogn了,不过如果是linkedlist的话,可以在每个node里存个index,remove就是o(1
)了
}
return result;
}
avatar
w*o
18
数组里可以有重复的数吗?
如果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]

avatar
T*8
19
不知道有没有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]
avatar
r*b
20
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]

avatar
l*i
21
divide and conquer, count each half and also sort them, then you can do O(
nlogn). I agree that O(n) seems unlikely.
avatar
w*y
22
55555 我怎么没看懂这个题目什么意思
avatar
t*7
23
用O(N)空间,COUNT SORT做前面COUNT那个PROCESS,出来的数组就是这个数字之前有几个
比他小的吧...这样行么?
avatar
q*8
24
nlogn吧,sort,然后binary search找。
avatar
P*U
25
binary search 的时候怎么做到只考虑右边的比它小的?

【在 q******8 的大作中提到】
: nlogn吧,sort,然后binary search找。
avatar
e*l
26
从后往前建堆. 记录新node移动的信息. 整个复杂度应该是build heap的时间,O(n)。
这样对不对?
avatar
c*g
27
应该是,BINARY SEARCH之后,就可以找到INDEX,这个INDEX就是小于它的个数吧

er) 的大作中提到: 】

【在 P*******U 的大作中提到】
: binary search 的时候怎么做到只考虑右边的比它小的?
avatar
P*U
28
是啊,但是题目要求Count smaller elements on right side,不是general的smaller
elements啊

【在 c***g 的大作中提到】
: 应该是,BINARY SEARCH之后,就可以找到INDEX,这个INDEX就是小于它的个数吧
:
: er) 的大作中提到: 】

avatar
s*n
29
维护一个bst,每个节点存子树的节点总数。
来一个数字后插入,旋转等,需要修改节点数。。
那么比这个数字小的节点总数为:
插入节点的左儿子节点数,加上所有祖先节点的左儿子节点数,向上查找祖先节点的终止条件是当前节点已经是父亲节点的左儿子。
avatar
e*l
30
从答案[3,5,3,3,0,2,1,0]推不出来排序的结果,所以先sort的话做了多余的操作。从
后往前建堆,虽然是n次lgn的binary search,但是这个级数能收敛到O(n)。你看书上
建堆的分析。这样应该是对的。
avatar
s*n
31
把一个数字插入堆中,如何知道堆中比这个数字小的集合总数?堆的特性是某一节点的
后代都比它小,但不代表所有比它小的都是它后代。

【在 e***l 的大作中提到】
: 从后往前建堆. 记录新node移动的信息. 整个复杂度应该是build heap的时间,O(n)。
: 这样对不对?

avatar
e*l
32
你说的对。我再想想

【在 s******n 的大作中提到】
: 把一个数字插入堆中,如何知道堆中比这个数字小的集合总数?堆的特性是某一节点的
: 后代都比它小,但不代表所有比它小的都是它后代。

avatar
q*8
33
int[] smaller_on_right(int[] array){
int length = array.length;
int[] result = new int[length];
ArrayList arraylist = new ArrayList();
for(int i=0; iarraylist.add(array[i]);
}
Collections.sort(arraylist);//nlgn
for(int j=0; jresult[j] = Collections.binarySearch(arraylist, array[j]);//lgn
arraylist.remove(result[j]);//这步如果是array的话,算法就不是
nlogn了,不过如果是linkedlist的话,可以在每个node里存个index,remove就是o(1
)了
}
return result;
}
avatar
w*o
34
数组里可以有重复的数吗?
如果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]

avatar
h*e
35
[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 我怎么没看懂这个题目什么意思
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。