z*z
发帖数: 837 | 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**t
发帖数: 2744 | 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*z
发帖数: 837 | 3 bubble is still O(n^2)
【在 c**t 的大作中提到】
: bubble is the simplest solution :-)
|
g**e
发帖数: 6127 | 4 啥意思，是能被另外一个数组的每一个数整除，还是只要有一个能整除就行了
【在 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?
|
d********e
发帖数: 132 | 5 我对这道题的第一感觉是：先sort, 后二分，
【在 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*z
发帖数: 837 | 6 只有一个整除就可以了。
【在 g**e 的大作中提到】
: 啥意思，是能被另外一个数组的每一个数整除，还是只要有一个能整除就行了
|
w******1
发帖数: 520 | 7 SORT没什么本质的作用吧？
如果ARRAY ONE: 3 51 71 9 11
ARRAY TWO: 2 4 16 28 10
怎么着也得都给遍历到了才能出个结果。
可不可以把两个ARRAY 合成一个， 加上来自于哪个ARRAY 的标记。
用二分法互除， 如果可以被除并且不是来自于同一个ARRAY ， 那么就RETURN.
NLOGN |
z*z
发帖数: 837 | 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**r
发帖数: 40 | 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****n
发帖数: 431 | 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****n
发帖数: 431 | 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*******y
发帖数: 1930 | 12 另外一个idea是，把B数组的每个数分解(分解为质数之积)，然后做成一个trie。不过
分解数本来就是hard的问题了，不过我看楼上的方法的复杂度(理论上)也不低 |
s*w
发帖数: 729 | 13 这个像面试风格的问题，需要多问几次，搞明白到底是啥问题
【在 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?
|
s***e
发帖数: 793 | 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***e
发帖数: 793 | 15 举一个例子
A 全部是质数
B 全部是质数
sqrt(Min(A)) > (Max(B))
还真不知道如何能优化。
【在 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?
|
s***e
发帖数: 793 | 16 对头，分解一个大质数的功夫都除完两边了
【在 g*******y 的大作中提到】
: 另外一个idea是，把B数组的每个数分解(分解为质数之积)，然后做成一个trie。不过
: 分解数本来就是hard的问题了，不过我看楼上的方法的复杂度(理论上)也不低
|
s*w
发帖数: 729 | 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 的大作中提到】
: 另外一个idea是，把B数组的每个数分解(分解为质数之积)，然后做成一个trie。不过
: 分解数本来就是hard的问题了，不过我看楼上的方法的复杂度(理论上)也不低
|
s***e
发帖数: 793 | 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**e
发帖数: 6127 | 19 分解质因数的时间说不定比brute force还长
【在 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
|
s*w
发帖数: 729 | 20 同意，不过那个时间貌似不算在 time complexity 里面，算法还是O(n)
【在 g**e 的大作中提到】
: 分解质因数的时间说不定比brute force还长
|
|
|
s***e
发帖数: 793 | 21 你对time complexity 的理解有问题，你对分解因式的理解也有问题
【在 s*w 的大作中提到】
: 同意，不过那个时间貌似不算在 time complexity 里面，算法还是O(n)
|
s*w
发帖数: 729 | 22 请指教，我的确是理解的比较肤浅，不大懂，破砖引玉
【在 s***e 的大作中提到】
: 你对time complexity 的理解有问题，你对分解因式的理解也有问题
|
p******r
发帖数: 2999 | 23 这么说吧，你不能只算外循环的复杂度而忽略了内循环
对于一个整数N，因式分解的复杂度是多少？
【在 s*w 的大作中提到】
: 请指教，我的确是理解的比较肤浅，不大懂，破砖引玉
|
s*w
发帖数: 729 | 24 是不是 O(N)?
最笨的从1到N 找因子，挨个测试是否被 N 整除
稍微好点的从1 到 N 找 prime number 因子，直到 sqrt(N)
【在 p******r 的大作中提到】
: 这么说吧，你不能只算外循环的复杂度而忽略了内循环
: 对于一个整数N，因式分解的复杂度是多少？
|
p******r
发帖数: 2999 | 25 如果这个整数非常大，估计找因子的开销就比解决问题本身的都要大
【在 s*w 的大作中提到】
: 是不是 O(N)?
: 最笨的从1到N 找因子，挨个测试是否被 N 整除
: 稍微好点的从1 到 N 找 prime number 因子，直到 sqrt(N)
|
s*w
发帖数: 729 | 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*********g
发帖数: 207 | 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 的大作中提到】
: "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?
|
H****r
发帖数: 2801 | 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 的大作中提到】
: "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?
|
