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]
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]
b*k
2 楼
5个独立的来自美国，英国，德国，意大利，新加坡。其中新加坡的是个中国人。两封
相关的都是中国人。
相关的都是中国人。
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]
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]
H*e
4 楼
我觉得没有问题。我记得有人有好几个中国的推荐人呢。
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.
nlogn). I agree that O(n) seems unlikely.
w*y
6 楼
55555 我怎么没看懂这个题目什么意思
t*7
7 楼
用O(N)空间,COUNT SORT做前面COUNT那个PROCESS,出来的数组就是这个数字之前有几个
比他小的吧...这样行么?
比他小的吧...这样行么?
q*8
8 楼
nlogn吧，sort，然后binary search找。
P*U
9 楼
binary search 的时候怎么做到只考虑右边的比它小的？
【在 q******8 的大作中提到】
: nlogn吧，sort，然后binary search找。
【在 q******8 的大作中提到】
: nlogn吧，sort，然后binary search找。
e*l
10 楼
从后往前建堆. 记录新node移动的信息. 整个复杂度应该是build heap的时间，O(n)。
这样对不对？
这样对不对？
c*g
11 楼
应该是，BINARY SEARCH之后，就可以找到INDEX，这个INDEX就是小于它的个数吧
er) 的大作中提到: 】
【在 P*******U 的大作中提到】
: binary search 的时候怎么做到只考虑右边的比它小的？
er) 的大作中提到: 】
【在 P*******U 的大作中提到】
: binary search 的时候怎么做到只考虑右边的比它小的？
P*U
12 楼
是啊，但是题目要求Count smaller elements on right side，不是general的smaller
elements啊
【在 c***g 的大作中提到】
: 应该是，BINARY SEARCH之后，就可以找到INDEX，这个INDEX就是小于它的个数吧
:
: er) 的大作中提到: 】
elements啊
【在 c***g 的大作中提到】
: 应该是，BINARY SEARCH之后，就可以找到INDEX，这个INDEX就是小于它的个数吧
:
: er) 的大作中提到: 】
s*n
13 楼
维护一个bst，每个节点存子树的节点总数。
来一个数字后插入，旋转等，需要修改节点数。。
那么比这个数字小的节点总数为：
插入节点的左儿子节点数，加上所有祖先节点的左儿子节点数，向上查找祖先节点的终止条件是当前节点已经是父亲节点的左儿子。
来一个数字后插入，旋转等，需要修改节点数。。
那么比这个数字小的节点总数为：
插入节点的左儿子节点数，加上所有祖先节点的左儿子节点数，向上查找祖先节点的终止条件是当前节点已经是父亲节点的左儿子。
e*l
14 楼
从答案[3,5,3,3,0,2,1,0]推不出来排序的结果，所以先sort的话做了多余的操作。从
后往前建堆，虽然是n次lgn的binary search，但是这个级数能收敛到O(n)。你看书上
建堆的分析。这样应该是对的。
后往前建堆，虽然是n次lgn的binary search，但是这个级数能收敛到O(n)。你看书上
建堆的分析。这样应该是对的。
s*n
15 楼
把一个数字插入堆中，如何知道堆中比这个数字小的集合总数？堆的特性是某一节点的
后代都比它小，但不代表所有比它小的都是它后代。
【在 e***l 的大作中提到】
: 从后往前建堆. 记录新node移动的信息. 整个复杂度应该是build heap的时间，O(n)。
: 这样对不对？
后代都比它小，但不代表所有比它小的都是它后代。
【在 e***l 的大作中提到】
: 从后往前建堆. 记录新node移动的信息. 整个复杂度应该是build heap的时间，O(n)。
: 这样对不对？
e*l
16 楼
你说的对。我再想想
【在 s******n 的大作中提到】
: 把一个数字插入堆中，如何知道堆中比这个数字小的集合总数？堆的特性是某一节点的
: 后代都比它小，但不代表所有比它小的都是它后代。
【在 s******n 的大作中提到】
: 把一个数字插入堆中，如何知道堆中比这个数字小的集合总数？堆的特性是某一节点的
: 后代都比它小，但不代表所有比它小的都是它后代。
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; i
}
Collections.sort(arraylist);//nlgn
for(int j=0; j
arraylist.remove(result[j]);//这步如果是array的话，算法就不是
nlogn了，不过如果是linkedlist的话，可以在每个node里存个index，remove就是o（1
）了
}
return result;
}
int length = array.length;
int[] result = new int[length];
ArrayList
for(int i=0; i
}
Collections.sort(arraylist);//nlgn
for(int j=0; j
arraylist.remove(result[j]);//这步如果是array的话，算法就不是
nlogn了，不过如果是linkedlist的话，可以在每个node里存个index，remove就是o（1
）了
}
return result;
}
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]
如果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
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]
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
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]
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
21 楼
divide and conquer, count each half and also sort them, then you can do O(
nlogn). I agree that O(n) seems unlikely.
nlogn). I agree that O(n) seems unlikely.
w*y
22 楼
55555 我怎么没看懂这个题目什么意思
t*7
23 楼
用O(N)空间,COUNT SORT做前面COUNT那个PROCESS,出来的数组就是这个数字之前有几个
比他小的吧...这样行么?
比他小的吧...这样行么?
q*8
24 楼
nlogn吧，sort，然后binary search找。
P*U
25 楼
binary search 的时候怎么做到只考虑右边的比它小的？
【在 q******8 的大作中提到】
: nlogn吧，sort，然后binary search找。
【在 q******8 的大作中提到】
: nlogn吧，sort，然后binary search找。
e*l
26 楼
从后往前建堆. 记录新node移动的信息. 整个复杂度应该是build heap的时间，O(n)。
这样对不对？
这样对不对？
c*g
27 楼
应该是，BINARY SEARCH之后，就可以找到INDEX，这个INDEX就是小于它的个数吧
er) 的大作中提到: 】
【在 P*******U 的大作中提到】
: binary search 的时候怎么做到只考虑右边的比它小的？
er) 的大作中提到: 】
【在 P*******U 的大作中提到】
: binary search 的时候怎么做到只考虑右边的比它小的？
P*U
28 楼
是啊，但是题目要求Count smaller elements on right side，不是general的smaller
elements啊
【在 c***g 的大作中提到】
: 应该是，BINARY SEARCH之后，就可以找到INDEX，这个INDEX就是小于它的个数吧
:
: er) 的大作中提到: 】
elements啊
【在 c***g 的大作中提到】
: 应该是，BINARY SEARCH之后，就可以找到INDEX，这个INDEX就是小于它的个数吧
:
: er) 的大作中提到: 】
s*n
29 楼
维护一个bst，每个节点存子树的节点总数。
来一个数字后插入，旋转等，需要修改节点数。。
那么比这个数字小的节点总数为：
插入节点的左儿子节点数，加上所有祖先节点的左儿子节点数，向上查找祖先节点的终止条件是当前节点已经是父亲节点的左儿子。
来一个数字后插入，旋转等，需要修改节点数。。
那么比这个数字小的节点总数为：
插入节点的左儿子节点数，加上所有祖先节点的左儿子节点数，向上查找祖先节点的终止条件是当前节点已经是父亲节点的左儿子。
e*l
30 楼
从答案[3,5,3,3,0,2,1,0]推不出来排序的结果，所以先sort的话做了多余的操作。从
后往前建堆，虽然是n次lgn的binary search，但是这个级数能收敛到O(n)。你看书上
建堆的分析。这样应该是对的。
后往前建堆，虽然是n次lgn的binary search，但是这个级数能收敛到O(n)。你看书上
建堆的分析。这样应该是对的。
s*n
31 楼
把一个数字插入堆中，如何知道堆中比这个数字小的集合总数？堆的特性是某一节点的
后代都比它小，但不代表所有比它小的都是它后代。
【在 e***l 的大作中提到】
: 从后往前建堆. 记录新node移动的信息. 整个复杂度应该是build heap的时间，O(n)。
: 这样对不对？
后代都比它小，但不代表所有比它小的都是它后代。
【在 e***l 的大作中提到】
: 从后往前建堆. 记录新node移动的信息. 整个复杂度应该是build heap的时间，O(n)。
: 这样对不对？
e*l
32 楼
你说的对。我再想想
【在 s******n 的大作中提到】
: 把一个数字插入堆中，如何知道堆中比这个数字小的集合总数？堆的特性是某一节点的
: 后代都比它小，但不代表所有比它小的都是它后代。
【在 s******n 的大作中提到】
: 把一个数字插入堆中，如何知道堆中比这个数字小的集合总数？堆的特性是某一节点的
: 后代都比它小，但不代表所有比它小的都是它后代。
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; i
}
Collections.sort(arraylist);//nlgn
for(int j=0; j
arraylist.remove(result[j]);//这步如果是array的话，算法就不是
nlogn了，不过如果是linkedlist的话，可以在每个node里存个index，remove就是o（1
）了
}
return result;
}
int length = array.length;
int[] result = new int[length];
ArrayList
for(int i=0; i
}
Collections.sort(arraylist);//nlgn
for(int j=0; j
arraylist.remove(result[j]);//这步如果是array的话，算法就不是
nlogn了，不过如果是linkedlist的话，可以在每个node里存个index，remove就是o（1
）了
}
return result;
}
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]
如果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
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 我怎么没看懂这个题目什么意思
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 我怎么没看懂这个题目什么意思
相关阅读
485 inforpass 归来转一百个包子到版面，版主帮发了吧请问 I-485 是寄到USPS的地址好，还是Courier 的地址好SR和Infopass得到这种回复-大家帮忙看正常吗？请问通过EB1B申请绿卡的话，对审稿的要求是怎样的？请教I485有关问题。NSC RD May 16 485 approved 1 hour ago(接包子啦)递交入籍申请后的等待期可不可以离开美国去旅行？求物理,材料（半导体）方向审稿机会这种情况要不要pp？TSC non-pp 140 EB1A请进急问，f2紧急回国，再签h4出来会有问题吗？请问换工作的绿卡问题 (转载)[Gone]]中文稿件审稿机会（免疫学杂志）需要大量的bless啊！EB1A写了几封推荐信485从decision变回initial reviewRFE recommendation letters485打持久战的童鞋，如何知道case被转到local office了？请问这样的独立引用值得列出来吗？