示例 1:
输入: [1,3,4,2,2]
输出: 2
示例 2:
输入: [3,1,3,4,2]
输出: 3
说明:
不能更改原数组(假设数组是只读的)。
只能使用额外的 O(1) 的空间。...数组中只有一个重复的数字,但它可能不止重复出现一次。
解:一种是二分法,然后遍历整个数组计算左边大于mid的数量和左边数的个数是否相同。...一种是龟兔算法快慢指针:
Floyd判圈算法
龟兔算法参考1
龟兔算法参考2
龟兔算法参考3
假设数组中没有重复,那我们可以做到这么一点,就是将数组的下标和1到n每一个数一对一的映射起来。...比如数组是213,则映射关系为0->2, 1->1, 2->3。假设这个一对一映射关系是一个函数f(n),其中n是下标,f(n)是映射到的数。...比如在这个例子中有两个下标的序列,0->2->3。
但如果有重复的话,这中间就会产生多对一的映射,比如数组2131,则映射关系为0->2, {1,3}->1, 2->3。