问个简单算法题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

问个简单算法题

问个简单算法题# JobHunting - 待字闺中

z*z2010-07-02 07:07

1 楼

"How to find whether an integer array has at least one
number which can be divided evenly (no remainder) by
another integer array?"
I can do it using a 2 for loop and it will be O(n^2).
The question is, is there a way to optimize the algorithm?

c*t2010-07-02 07:07

2 楼

bubble is the simplest solution :-)

【在 z*z 的大作中提到】

: "How to find whether an integer array has at least one
: number which can be divided evenly (no remainder) by
: another integer array?"
: I can do it using a 2 for loop and it will be O(n^2).
: The question is, is there a way to optimize the algorithm?

z*z2010-07-02 07:07

3 楼

bubble is still O(n^2)

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

: bubble is the simplest solution :-)

g*e2010-07-02 07:07

4 楼

啥意思，是能被另外一个数组的每一个数整除，还是只要有一个能整除就行了

【在 z*z 的大作中提到】

d*e2010-07-02 07:07

5 楼

我对这道题的第一感觉是：先sort, 后二分，

【在 z*z 的大作中提到】

z*z2010-07-02 07:07

6 楼

只有一个整除就可以了。

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

: 啥意思，是能被另外一个数组的每一个数整除，还是只要有一个能整除就行了

w*12010-07-02 07:07

7 楼

SORT没什么本质的作用吧？
如果ARRAY ONE: 3 51 71 9 11
ARRAY TWO: 2 4 16 28 10
怎么着也得都给遍历到了才能出个结果。
可不可以把两个ARRAY 合成一个，加上来自于哪个ARRAY 的标记。
用二分法互除，如果可以被除并且不是来自于同一个ARRAY ，那么就RETURN.
NLOGN

z*z2010-07-02 07:07

8 楼

这听着还reasonable一些，不过这要把每个整数变成一个struct了，
好像复杂了一些。
我电面的时候也是说sort再二分，不过实话说具体二分怎么做我也
不清楚，好像HM不是很满意。

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

: SORT没什么本质的作用吧？
: 如果ARRAY ONE: 3 51 71 9 11
: ARRAY TWO: 2 4 16 28 10
: 怎么着也得都给遍历到了才能出个结果。
: 可不可以把两个ARRAY 合成一个，加上来自于哪个ARRAY 的标记。
: 用二分法互除，如果可以被除并且不是来自于同一个ARRAY ，那么就RETURN.
: NLOGN

i*r2010-07-02 07:07

9 楼

If I understand your problem correctly, The problem can be formulated as:
Input: Integer array A, and B
output: find an element in A that is divisible by every element in B
Algorithm:
Step1, c = lcm(B) // least common multiple of all elements in B
step2, foreach a in A, test if c|a
if the integers in B have range limits, step1 takes O(n) time, then we get a
algorithm with linear time complexity.

g*n2010-07-02 07:07

10 楼

这题应该不是在A中找一个数，使其能整除B中的所有数。否则的话，题目就暗示了首先
求B数组最大公约
数，然后遍历A，找一个能整除这个最大公约数的数。这样太简单了。

as:
get a

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

: If I understand your problem correctly, The problem can be formulated as:
: Input: Integer array A, and B
: output: find an element in A that is divisible by every element in B
: Algorithm:
: Step1, c = lcm(B) // least common multiple of all elements in B
: step2, foreach a in A, test if c|a
: if the integers in B have range limits, step1 takes O(n) time, then we get a
: algorithm with linear time complexity.

g*n2010-07-02 07:07

11 楼

我想到一个办法：
假设从A数组中找一个数，使其能整除B数组中的一个数。先把B排序，从小到大。遍历A
，对于A中的每一
个数a，设n=B[0]/a, m=B[MAX]/a。这样如果B中有一个数能被a整除，除完以后的倍数
一定在[n,
m]之间。现在遍历i = n->m，在B中二分查找a*i即可。
时间复杂度是|A|*K*Log(|B|), K为B中最大元素除以A中最小元素得到的商。

【在 z*z 的大作中提到】

: 这听着还reasonable一些，不过这要把每个整数变成一个struct了，
: 好像复杂了一些。
: 我电面的时候也是说sort再二分，不过实话说具体二分怎么做我也
: 不清楚，好像HM不是很满意。

g*y2010-07-02 07:07

12 楼

另外一个idea是，把B数组的每个数分解(分解为质数之积)，然后做成一个trie。不过
分解数本来就是hard的问题了，不过我看楼上的方法的复杂度(理论上)也不低

s*w2010-07-02 07:07

13 楼

这个像面试风格的问题，需要多问几次，搞明白到底是啥问题

【在 z*z 的大作中提到】

s*e2010-07-02 07:07

14 楼

K可能远远大于|B|

历A

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

: 我想到一个办法：
: 假设从A数组中找一个数，使其能整除B数组中的一个数。先把B排序，从小到大。遍历A
: ，对于A中的每一
: 个数a，设n=B[0]/a, m=B[MAX]/a。这样如果B中有一个数能被a整除，除完以后的倍数
: 一定在[n,
: m]之间。现在遍历i = n->m，在B中二分查找a*i即可。
: 时间复杂度是|A|*K*Log(|B|), K为B中最大元素除以A中最小元素得到的商。

s*e2010-07-02 07:07

15 楼

举一个例子
A 全部是质数
B 全部是质数
sqrt(Min(A)) > (Max(B))
还真不知道如何能优化。

【在 z*z 的大作中提到】

s*e2010-07-02 07:07

16 楼

对头，分解一个大质数的功夫都除完两边了

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

: 另外一个idea是，把B数组的每个数分解(分解为质数之积)，然后做成一个trie。不过
: 分解数本来就是hard的问题了，不过我看楼上的方法的复杂度(理论上)也不低

s*w2010-07-02 07:07

17 楼

我有一个类似的主意，
把 A 存成 hash table
遍历 B, 对每个 B 元素，分解出所有的因子，check 是否 any 因子 in A's hash
table
worse case O(n) complexity, where n is size of B

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

s*e2010-07-02 07:07

18 楼

分解一个unsigned long integer 的worst case是多少？

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

: 我有一个类似的主意，
: 把 A 存成 hash table
: 遍历 B, 对每个 B 元素，分解出所有的因子，check 是否 any 因子 in A's hash
: table
: worse case O(n) complexity, where n is size of B

g*e2010-07-02 07:07

19 楼

分解质因数的时间说不定比brute force还长

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

s*w2010-07-02 07:07

20 楼

同意，不过那个时间貌似不算在 time complexity 里面，算法还是O(n)

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

: 分解质因数的时间说不定比brute force还长

s*e2010-07-02 07:07

21 楼

你对time complexity 的理解有问题，你对分解因式的理解也有问题

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

: 同意，不过那个时间貌似不算在 time complexity 里面，算法还是O(n)

s*w2010-07-02 07:07

22 楼

请指教，我的确是理解的比较肤浅，不大懂，破砖引玉

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

: 你对time complexity 的理解有问题，你对分解因式的理解也有问题

p*r2010-07-02 07:07

23 楼

这么说吧，你不能只算外循环的复杂度而忽略了内循环
对于一个整数N，因式分解的复杂度是多少？

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

: 请指教，我的确是理解的比较肤浅，不大懂，破砖引玉

s*w2010-07-02 07:07

24 楼

是不是 O(N)?
最笨的从1到N 找因子，挨个测试是否被 N 整除
稍微好点的从1 到 N 找 prime number 因子，直到 sqrt(N)

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

: 这么说吧，你不能只算外循环的复杂度而忽略了内循环
: 对于一个整数N，因式分解的复杂度是多少？

p*r2010-07-02 07:07

25 楼

如果这个整数非常大，估计找因子的开销就比解决问题本身的都要大

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

: 是不是 O(N)?
: 最笨的从1到N 找因子，挨个测试是否被 N 整除
: 稍微好点的从1 到 N 找 prime number 因子，直到 sqrt(N)

s*w2010-07-02 07:07

26 楼

Agree, 刚才狗了一下
When the numbers are very large, no efficient integer factorization
algorithm is publicly known; an effort concluded in 2009 by several
researchers factored a 232-digit number (RSA-768) utilizing hundreds of
machines over a span of 2 years
看来有必要把整数的range考虑进去，原问题的复杂度就变成了 O(nN), 在N > n 的情
况下，的确不值得
有没有原问题正确的解答？

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

: 如果这个整数非常大，估计找因子的开销就比解决问题本身的都要大

f*g2010-07-02 07:07

27 楼

想到一个办法，类似randix sort。假设A中最大，最小数分别为Amax,Amin,将A hash
到size为Amax-Amin＋1的数组,设为H,H[i]=1 if Amin+i在A中，否则为零。然后对B中
每一个数，依次检验H[([Amin/Bi]，[Amin/Bi]+1,....[Amax/Bi])*Bi]是否为1。这样
假设A,B中的数组均值差不多，计算量为O(NA+NB)

【在 z*z 的大作中提到】

H*r2010-07-02 07:07

28 楼

How about:
A(M), B(N)
1) Find lsmA,least common multiple of all elements in A -- O(M)
2) Test if lsmA/B[i] == 0 -- O(N)
Then the complexity is O(M+N).

【在 z*z 的大作中提到】