IBM Ponder This #069 · 2004 年 1 月

本题由 Joe Buhler 提供，经 Eric Roberts 转述自 SIGCSE 会议。

一个只读数组长度为 n，下标为 1 至 n，每个元素都属于 {1,2,…,n-1}。由抽屉原理，至少有一个值重复。

设计一个线性时间算法，输出某个重复值，只允许使用常数额外空间。具体地说，只有固定数量的可读写存储单元，每个单元能存放 1 至 n 的整数，单元数不得依赖 n。原数组不能修改。算法应易于用常见编程语言实现。

解答

认真尝试后再打开

待补充。