x**********z
发帖数: 131 | 1 刚看到一道面试题：
给定一个整数N，一个整数array有m个元素，问把这个array里数字的倍数从1~N中去除
，剩下几个数字。只要个数不要具体剩哪些；N可能会有10^9量级。
谁有比较好的优于O(m*N)的解法？
感觉求最小公倍数什么的可以做，但是好复杂想不清楚了。。。 |
x******r
发帖数: 3489 | 2 把这个array里数字的倍数从1~N中去除？
are you sure the description of the question is right? |
b***e
发帖数: 1419 | 3 merge sort可以做到O(N*log(m))。
无脑容斥可以到O(2^m)。
如果array两两互斥且值不大，可以考虑孙子定理。
这个你要给一些test case才好说什么方法比较好。
【在 x**********z 的大作中提到】
: 刚看到一道面试题：
: 给定一个整数N，一个整数array有m个元素，问把这个array里数字的倍数从1~N中去除
: ，剩下几个数字。只要个数不要具体剩哪些；N可能会有10^9量级。
: 谁有比较好的优于O(m*N)的解法？
: 感觉求最小公倍数什么的可以做，但是好复杂想不清楚了。。。
|
A*******e
发帖数: 2419 | 4 怎么总贴些描述不清楚的题目。浪费时间。
【在 x**********z 的大作中提到】
: 刚看到一道面试题：
: 给定一个整数N，一个整数array有m个元素，问把这个array里数字的倍数从1~N中去除
: ，剩下几个数字。只要个数不要具体剩哪些；N可能会有10^9量级。
: 谁有比较好的优于O(m*N)的解法？
: 感觉求最小公倍数什么的可以做，但是好复杂想不清楚了。。。
|
x**********z
发帖数: 131 | 5
描述不清吗？那我加个例子。
【在 x******r 的大作中提到】
: 把这个array里数字的倍数从1~N中去除？
: are you sure the description of the question is right?
|
x******8
发帖数: 48 | 6 不就是找小于数组最大数的所有质数的数量吗
(
【在 x**********z 的大作中提到】
: 刚看到一道面试题：
: 给定一个整数N，一个整数array有m个元素，问把这个array里数字的倍数从1~N中去除
: ，剩下几个数字。只要个数不要具体剩哪些；N可能会有10^9量级。
: 谁有比较好的优于O(m*N)的解法？
: 感觉求最小公倍数什么的可以做，但是好复杂想不清楚了。。。
|
x**********z
发帖数: 131 | 7
不一定哦。。
【在 x******8 的大作中提到】
: 不就是找小于数组最大数的所有质数的数量吗
:
: (
|
x**********z
发帖数: 131 | 8 刚看到一道面试题：
给定一个整数N，一个整数array有m个元素，问把这个array里数字的倍数从1~N中去除
，剩下几个数字。只要个数不要具体剩哪些；N可能会有10^9量级。
比如 N=10, array=[2,3]
因为 2 (2的倍数), 3 (3的倍数), 4 (2的倍数), 6 (2和3的倍数), 8 (2的倍数), 9 (
3的倍数) ,10 (2的倍数) 要被去除，剩下 1,5,7, 所以返回3.
谁有比较好的优于O(m*N)的解法？
感觉求最小公倍数什么的可以做，但是好复杂想不清楚了。。。 |
x******r
发帖数: 3489 | 9 把这个array里数字的倍数从1~N中去除？
are you sure the description of the question is right? |
b***e
发帖数: 1419 | 10 merge sort可以做到O(N*log(m))。
无脑容斥可以到O(2^m)。
如果array两两互斥且值不大，可以考虑孙子定理。
这个你要给一些test case才好说什么方法比较好。
【在 x**********z 的大作中提到】
: 刚看到一道面试题：
: 给定一个整数N，一个整数array有m个元素，问把这个array里数字的倍数从1~N中去除
: ，剩下几个数字。只要个数不要具体剩哪些；N可能会有10^9量级。
: 比如 N=10, array=[2,3]
: 因为 2 (2的倍数), 3 (3的倍数), 4 (2的倍数), 6 (2和3的倍数), 8 (2的倍数), 9 (
: 3的倍数) ,10 (2的倍数) 要被去除，剩下 1,5,7, 所以返回3.
: 谁有比较好的优于O(m*N)的解法？
: 感觉求最小公倍数什么的可以做，但是好复杂想不清楚了。。。
|
|
|
A*******e
发帖数: 2419 | 11 怎么总贴些描述不清楚的题目。浪费时间。
【在 x**********z 的大作中提到】
: 刚看到一道面试题：
: 给定一个整数N，一个整数array有m个元素，问把这个array里数字的倍数从1~N中去除
: ，剩下几个数字。只要个数不要具体剩哪些；N可能会有10^9量级。
: 比如 N=10, array=[2,3]
: 因为 2 (2的倍数), 3 (3的倍数), 4 (2的倍数), 6 (2和3的倍数), 8 (2的倍数), 9 (
: 3的倍数) ,10 (2的倍数) 要被去除，剩下 1,5,7, 所以返回3.
: 谁有比较好的优于O(m*N)的解法？
: 感觉求最小公倍数什么的可以做，但是好复杂想不清楚了。。。
|
x**********z
发帖数: 131 | 12
描述不清吗？那我加个例子。
【在 x******r 的大作中提到】
: 把这个array里数字的倍数从1~N中去除？
: are you sure the description of the question is right?
|
x******8
发帖数: 48 | 13 不就是找小于数组最大数的所有质数的数量吗
(
【在 x**********z 的大作中提到】
: 刚看到一道面试题：
: 给定一个整数N，一个整数array有m个元素，问把这个array里数字的倍数从1~N中去除
: ，剩下几个数字。只要个数不要具体剩哪些；N可能会有10^9量级。
: 比如 N=10, array=[2,3]
: 因为 2 (2的倍数), 3 (3的倍数), 4 (2的倍数), 6 (2和3的倍数), 8 (2的倍数), 9 (
: 3的倍数) ,10 (2的倍数) 要被去除，剩下 1,5,7, 所以返回3.
: 谁有比较好的优于O(m*N)的解法？
: 感觉求最小公倍数什么的可以做，但是好复杂想不清楚了。。。
|
x**********z
发帖数: 131 | 14
不一定哦。。
【在 x******8 的大作中提到】
: 不就是找小于数组最大数的所有质数的数量吗
:
: (
|
s******y
发帖数: 205 | |
h**********c
发帖数: 4120 | 16 我老狂妄地打断如火如荼热恋班的辩论，
unique factorial theorem,
来观众盆有们，掌声鼓励！ |
h**********c
发帖数: 4120 | 17 factorial, factorization,丢脸了。
老型你这个版不行啊！
【在 h**********c 的大作中提到】
: 我老狂妄地打断如火如荼热恋班的辩论，
: unique factorial theorem,
: 来观众盆有们，掌声鼓励！
|
