问一道面试题 - 未名空间MITBBS历史存档

x*z2015-07-12 07:07

1 楼

刚看到一道面试题：
给定一个整数N，一个整数array有m个元素，问把这个array里数字的倍数从1~N中去除
，剩下几个数字。只要个数不要具体剩哪些；N可能会有10^9量级。
谁有比较好的优于O(m*N)的解法？
感觉求最小公倍数什么的可以做，但是好复杂想不清楚了。。。

x*r2015-07-12 07:07

2 楼

把这个array里数字的倍数从1~N中去除？
are you sure the description of the question is right?

b*e2015-07-12 07:07

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*e2015-07-12 07:07

4 楼

怎么总贴些描述不清楚的题目。浪费时间。

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

: 刚看到一道面试题：
: 给定一个整数N，一个整数array有m个元素，问把这个array里数字的倍数从1~N中去除
: ，剩下几个数字。只要个数不要具体剩哪些；N可能会有10^9量级。
: 谁有比较好的优于O(m*N)的解法？
: 感觉求最小公倍数什么的可以做，但是好复杂想不清楚了。。。

x*z2015-07-12 07:07

5 楼

描述不清吗？那我加个例子。

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

: 把这个array里数字的倍数从1~N中去除？
: are you sure the description of the question is right?

x*82015-07-12 07:07

6 楼

不就是找小于数组最大数的所有质数的数量吗

(

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

: 刚看到一道面试题：
: 给定一个整数N，一个整数array有m个元素，问把这个array里数字的倍数从1~N中去除
: ，剩下几个数字。只要个数不要具体剩哪些；N可能会有10^9量级。
: 谁有比较好的优于O(m*N)的解法？
: 感觉求最小公倍数什么的可以做，但是好复杂想不清楚了。。。

x*z2015-07-12 07:07

7 楼

不一定哦。。

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

: 不就是找小于数组最大数的所有质数的数量吗
:
: (

x*z2015-07-12 07:07

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*r2015-07-12 07:07

9 楼

把这个array里数字的倍数从1~N中去除？
are you sure the description of the question is right?

b*e2015-07-12 07:07

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*e2015-07-12 07:07

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*z2015-07-12 07:07

12 楼

描述不清吗？那我加个例子。

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

: 把这个array里数字的倍数从1~N中去除？
: are you sure the description of the question is right?

x*82015-07-12 07:07

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*z2015-07-12 07:07

14 楼

不一定哦。。

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

: 不就是找小于数组最大数的所有质数的数量吗
:
: (

s*y2015-07-12 07:07

15 楼

LZ最后找到答案了吗？

h*c2015-07-12 07:07

16 楼

我老狂妄地打断如火如荼热恋班的辩论，
unique factorial theorem,
来观众盆有们，掌声鼓励！

h*c2015-07-12 07:07

17 楼

factorial, factorization,丢脸了。
老型你这个版不行啊！

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

: 我老狂妄地打断如火如荼热恋班的辩论，
: unique factorial theorem,
: 来观众盆有们，掌声鼓励！