求问Jane Street一道面试题

原帖地址:mitbbs

有个大小为n+1的数组,数组中的每个元素是[1,n],所以至少有两个是重复的。例如n=
4, 数组为[2,3,4,1,1]或者[2,3,1,1,1],要求找出重复的那个数字。复杂度要求:空
间O(1), 时间复杂度:小于O(n^2)。不能改变原来数组。

请各位看清题目再回复,和LC的题目不一样。