IBM挑戰2004年1月原文

Ponder This Challenge: This month's puzzle was sent in by Joe Buhler.
It came from a SIGCSE meeting via Eric Roberts.



A read-only array of length n, with address from 1 to n inclusive,
contains entries from the set {1, 2, ..., n-1}.
By Dirichlet's Pigeon-Hole Principle there are one or more duplicated
entries. Find a linear-time algorithm that prints a duplicated value,
using only "constant extra space". (This space restriction is
important; we have only a fixed finite number of usable read/write
memory locations, each capable of storing an integer between 1 and n.
The original array entries can not be altered.) The algorithm should
be easily implementable in any standard programming language.
一个长度为n的唯读阵列(位址为1至n)所包含的元素是整数，每个元素的大小是由1至n-1。由鴿巢原理，至少有兩个不同位址的元素值是重复的。
请作出一个算法，以列印出其中一个重复的元素值。条件是：
1. 算法运行所需的时间是线性的；
2. 只有固定有限个記憶位址可供读寫之用，每个記憶位址只可儲存一个大小是由1至n的整数；
3. 原阵列不能修改；
4. 算法应该以任何標準程式語言都可容易施行。

不能求和？ 然后减去S（1～（n－1））

明确一下吧，楼主也不说话的
对矩阵各位相加求和，然后减去 1～N－1 的和就得出重复的数值了

晕倒～～

看见这样的题目，哦只有吐血而S的份了

连题目哦都看不懂~~

卉mm就是这么可爱 术业有专攻嘛。

没那个水平，只能分析难点了：
1、只读数组：意味着不能排序
2、并非只能有两个个重复的值（可以同时有3个1、2个8、7个109…）：累加算法无用

一般直接比较的算法，复杂度都不可能是线性的

鸽巢原理说的是-至少-
算法时间的线性是要重点考虑的

嘿嘿,又想了一下,晕了
复杂的远远超出了
数学没学好,后悔呀

呵呵 这下明白题目了 ：）
得想想了。。。。。。

那这样行不行？：
假设原矩阵为OLD，这样各元素表示为OLD(x) 1<=x<=(n-1)

建立位址为 1～n－1 的线性矩阵 NEW，预置所有值为零

For x= 1 to n-1
If NEW(OLD(x)) =0
Then NEW(OLD(x)) =1
Else Print（OLD(x））


只是把现有矩阵里面的值转换为新矩阵的下标来记录 第一次读到则置为1
下次读到则输出
你看行不行？