程序竞赛

constant · 发表于 2005-11-28 04:54:30

难度：++++

一个长为n的数组，里面的数为1到n-1的整数。找出一个重复的值。

不够难？能够用的存储单元有限制：存在一个与n无关的c，使用的存储单元不超过c*log(n)。例如n是64位整数时，使用的存储单元不能超过8c bytes，即最多存c个64位整数。

乱弹 · 发表于 2005-11-28 15:44:41

这些数存在哪里呢？就是计算空间复杂度的时候，计不计入图灵机上input tape 的空间使用数。

当然我猜想你这里是要求用实际的程序，不过也有类似问题。

constant · 发表于 2005-11-28 19:42:02

数组是 read only 的。可用内存是指数组以外能存能取的部分。

还忘了一个条件：程序的速度要求是 O(n)。

QL · 发表于 2005-12-1 05:00:52

Interesting question, can you hold off posting your answer?

constant · 发表于 2005-12-1 05:32:04

Sure. How long do you need?

QL · 发表于 2005-12-1 07:11:09

Hmmm, another ++++ problem. I'd like to try to solve them in the same order as they were raised.

Archi · 发表于 2005-12-4 11:08:24

If there is only one redundant number, sum up the array. The number is Sum(array)-(1+2+..+(n-1)).

If there are two redundant numbers, calculate the usual sum and the sum of squares, we can resolve the two redundant numbers by solving two equations.

If the number of redundant numbers is unspecified and n can be arbitrarily large, I don't know how to do it in O(n).

		自动登录	找回密码
密码			立即注册

动态微博

程序竞赛

一点疑问

回复：一点疑问

回复：程序竞赛

Sure. How long do you need?

回复：Sure. How long do you need?

The problem is confusing