大家都材料都是寄到TX的吗？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Immigration - 落地生根

大家都材料都是寄到TX的吗？

大家都材料都是寄到TX的吗？# Immigration - 落地生根

l*r2012-10-22 07:10

1 楼

Given 3 sorted arrays, array a, array b, array c. find all pairs where a[i]
+ b[j] = c[k].
We can convert it to 3SUM for a nxn solution, but that doesn't used the "
sorted" property.

w*r2012-10-22 07:10

2 楼

我的case是属于NSC的，看到律师给的邮寄地址是TX的。是不是大家的case都先寄到TX
然后转送到NSC的？谢谢。
EB1-A,今天终于要寄出了，bless!

x*g2012-10-22 07:10

3 楼

参考这个http://www.mitbbs.com/article_t/JobHunting/32619751.html
我觉得矩阵的思路正确可以做到n*log(n)

e*r2012-10-22 07:10

4 楼

和你律师再核对一遍吧。按照140官方instruction的地址来。如果是140的话，你属于
NSC，我想不出有什么理由可以寄到TX。
Bless

TX

【在 w**********r 的大作中提到】

: 我的case是属于NSC的，看到律师给的邮寄地址是TX的。是不是大家的case都先寄到TX
: 然后转送到NSC的？谢谢。
: EB1-A,今天终于要寄出了，bless!

r*c2012-10-22 07:10

5 楼

怎么可能nlogn
可以有O（n^2)组解

x*g2012-10-22 07:10

6 楼

排序数组本身无dup?

【在 r****c 的大作中提到】

: 怎么可能nlogn
: 可以有O（n^2)组解

e*s2012-10-22 07:10

7 楼

这题用两个hash应该可以O(max(m,n) + l)，m, n, l分别是a, b, c的长度。

x*g2012-10-22 07:10

8 楼

展开说说，表示不解. hash求和的新思路也有兴趣学习，呵呵。
最差怎么都是o(n^2)
即使每个都无dup,像
A=1,2,3,4,5...n
B=n,n-1,....1
C=n+1,n+2......n+n
那么n+1就有n对
n+2就n-1对
...n+n就1对
计算n(n+1)/2.....

【在 e***s 的大作中提到】

: 这题用两个hash应该可以O(max(m,n) + l)，m, n, l分别是a, b, c的长度。

e*s2012-10-22 07:10

9 楼

之前看错题了，以为返回是否存在a[i] + b[j] = c[k]
但是复杂度是一样的。
public static boolean another3Sum(int[] A, int[] B, int[] C){
HashSet ha = new HashSet();
HashSet hb = new HashSet();
int i = 0, j = 0;
for(int k = 0; k < C.length; k++){
if(i < A.length && j < B.length){
if(A[i] + B[j] > C[k]){
if(ha.contains(C[k] - B[j]) || hb.contains(C[k] - A[i]))
return true;
}
else if (A[i] + B[j] < C[k]){
ha.add(A[i++]);
hb.add(B[j++]);
k--;
}
else return true;
} else if(i >= A.length){
if(ha.contains(C[k] - B[j])) return true;
else{
hb.add(B[j++]);
k--;
}
} else if(j >= B.length){
if(hb.contains(C[k] - A[i])) return true;
else{
ha.add(A[i++]);
k--;
}
}
}
return false;
}

【在 x****g 的大作中提到】

: 展开说说，表示不解. hash求和的新思路也有兴趣学习，呵呵。
: 最差怎么都是o(n^2)
: 即使每个都无dup,像
: A=1,2,3,4,5...n
: B=n,n-1,....1
: C=n+1,n+2......n+n
: 那么n+1就有n对
: n+2就n-1对
: ...n+n就1对
: 计算n(n+1)/2.....

x*g2012-10-22 07:10

10 楼

这个显然不一样。
代码没细看，但觉得不可能对。
简单举个例子：
a[0]=3;
b[0]=4;
c[0]=6
所以冲上来
a[i]+b[j]>c[k]
但是不能满足
if(ha.contains(C[k] - B[j]) || hb.contains(C[k] - A[i]))
return true;
完了直接死循环了.....
懒得琢磨了，呵呵。

))

【在 e***s 的大作中提到】

: 之前看错题了，以为返回是否存在a[i] + b[j] = c[k]
: 但是复杂度是一样的。
: public static boolean another3Sum(int[] A, int[] B, int[] C){
: HashSet ha = new HashSet();
: HashSet hb = new HashSet();
: int i = 0, j = 0;
: for(int k = 0; k < C.length; k++){
: if(i < A.length && j < B.length){
: if(A[i] + B[j] > C[k]){
: if(ha.contains(C[k] - B[j]) || hb.contains(C[k] - A[i]))

e*s2012-10-22 07:10

11 楼

我晕了，test case你跑过不？

【在 x****g 的大作中提到】

: 这个显然不一样。
: 代码没细看，但觉得不可能对。
: 简单举个例子：
: a[0]=3;
: b[0]=4;
: c[0]=6
: 所以冲上来
: a[i]+b[j]>c[k]
: 但是不能满足
: if(ha.contains(C[k] - B[j]) || hb.contains(C[k] - A[i]))

g*12012-10-22 07:10

12 楼

我觉得外星人挺有道理
不过好像在处理a或b到头时要考虑k++的情况

【在 x****g 的大作中提到】

x*g2012-10-22 07:10

13 楼

确实，我没能理解对，挺好的，继续学习中。

【在 g****1 的大作中提到】

: 我觉得外星人挺有道理
: 不过好像在处理a或b到头时要考虑k++的情况

l*r2012-10-22 07:10

14 楼

没搞懂. 大侠可不可以在明确一点?

g*12012-10-22 07:10

15 楼

嗯，好像有问题。一旦 a[i]+b[j]>c[k] 导致k++, 就失去了以后比较c[k]的机会

【在 x****g 的大作中提到】

: 确实，我没能理解对，挺好的，继续学习中。

e*s2012-10-22 07:10

16 楼

因为3个数组都是sorted的， a[i]+b[j] > c[k] 证明 c[k] 肯定不能由a[0..i]和b[0.
.j]组合而成。

【在 g****1 的大作中提到】

: 嗯，好像有问题。一旦 a[i]+b[j]>c[k] 导致k++, 就失去了以后比较c[k]的机会

b*f2012-10-22 07:10

17 楼

Mark

x*g2012-10-22 07:10

18 楼

但是c[k]失去了由a[0..i]和b[j+1....n]或者a[i+1...]和b[0...j]构成的判定机会？
a 2 5 6
b 1 3 10
c 7 9
开始i=0;j=0;k=0;
2+1 < 7 所以 i++,j++,k不动
5+3 > 7 所以判定7-5,7-3失败，这个时候k++
所以7从此失去了判定的机会？没机会判出6+1=7这一项了。
不知道我看错没，不能怪我啊，这个写的太邪乎，呵呵。

0.

【在 e***s 的大作中提到】

: 因为3个数组都是sorted的， a[i]+b[j] > c[k] 证明 c[k] 肯定不能由a[0..i]和b[0.
: .j]组合而成。

e*s2012-10-22 07:10

19 楼

确实是这样，我错了。
我也没想到能比 O(min(m * n, l))更好的了，m, n是3个数组长度较短的两个。

【在 x****g 的大作中提到】

: 但是c[k]失去了由a[0..i]和b[j+1....n]或者a[i+1...]和b[0...j]构成的判定机会？
: a 2 5 6
: b 1 3 10
: c 7 9
: 开始i=0;j=0;k=0;
: 2+1 < 7 所以 i++,j++,k不动
: 5+3 > 7 所以判定7-5,7-3失败，这个时候k++
: 所以7从此失去了判定的机会？没机会判出6+1=7这一项了。
: 不知道我看错没，不能怪我啊，这个写的太邪乎，呵呵。
:

s*t2012-10-22 07:10

20 楼

我来写个最靠谱的：
先用young，O(n)搞定每一个c[k],一共n个c[k],O(n2)
不过没有利用上sorted的c这个条件，估计还是不太好。。。嘻嘻