关于那个经典的missing number的题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

关于那个经典的missing number的题

关于那个经典的missing number的题# JobHunting - 待字闺中

c*t2011-06-28 07:06

1 楼

到底是什么？哪里有具体的描述？
是不是指的是下面的三个问题？
1. 给定数组size 是 n-1, 1,....n中的一个数missing, 求如何找出那个missing
number?
2. 给定数组size 是 n-2, 1,....n中的两个数missing, 求如何找出那两个missing
numbers?
3. 给定数组size 是 n-m, 1,....n中的m个数missing, 求如何找出那个m个missing
numbers? (假设 m < n/2).
是不是上面的题都有O(n) solution?

A*M2011-06-28 07:06

2 楼

都是O(n)吧，至少可以用辅助数组counting
1)简单点，直接用1-n总和减去数组里的所有数

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

: 到底是什么？哪里有具体的描述？
: 是不是指的是下面的三个问题？
: 1. 给定数组size 是 n-1, 1,....n中的一个数missing, 求如何找出那个missing
: number?
: 2. 给定数组size 是 n-2, 1,....n中的两个数missing, 求如何找出那两个missing
: numbers?
: 3. 给定数组size 是 n-m, 1,....n中的m个数missing, 求如何找出那个m个missing
: numbers? (假设 m < n/2).
: 是不是上面的题都有O(n) solution?