题目描述（中等难度）

将 到 n 范围内的某些数，放到大小为 n + 1 的数组中，数组要放满，所以一定会有一个重复的数字，找出这个重复的数字。比如 [2,2,2,1]。

假设重复的数字只有一个。

解法一和解法二先不考虑题目中 Note 的要求。

解法一 排序

最简单的，先排序，然后两两判断即可。

解法二 HashSet

判断重复数字，可以用 HashSet，这个方法经常用了。

  1. public int findDuplicate(int[] nums) {
  2.     HashSet<Integer> set = new HashSet<>();
  3.     for (int i = 0; i < nums.length; i++) {
  4.         if (set.contains(nums[i])) {
  5.             return nums[i];
  6.         }
  7.         set.add(nums[i]);
  8.     }
  9.     return -1;

解法三 二分查找

参考 %3A-O(nlog(n)) 。

我们知道二分查找要求有序，但是给定的数组不是有序的，那么怎么用二分查找呢？

原数组不是有序，但是我们知道重复的那个数字肯定是 1 到 n 中的某一个，而 1,2...,n 就是一个有序序列。因此我们可以对 1,2...,n 进行二分查找。

mid = (1 + n) / 2，接下来判断最终答案是在 [1, mid] 中还是在 [mid + 1, n] 中。

我们只需要统计原数组中小于等于 mid 的个数，记为 count。

如果 count > mid ，鸽巢原理，在 [1,mid] 范围内的数字个数超过了 mid ，所以一定有一个重复数字。

解法四 二进制

参考 -solution-using-bit-manipulation-in-10-lines)。137 题 以及 其实已经用过这个思想，但还是不容易往这方面想。

主要就是我们要把数字放眼到二进制。

然后依次统计数组中每一位 1 的个数，记为 a[i]。再依次统计 1 到 n 中每一位 1 的个数，记为 b[i]。 代表的是哪一位，因为是 int，所以范围是 0 到 32。

记重复的数字是 res。

如果 a[i] > b[i] 也就意味着 res 当前位是 1。

否则的话，res 当前位就是 0。

举个例子吧，1 3 4 2 2。

  1. 1 3 4 2 2 写成 2 进制
  2. 1 [0 0 1]
  3. 3 [0 1 1]
  4. 4 [1 0 0]
  5. 2 [0 1 0]
  6. 2 [0 1 0]
  8. 把 1 到 n,也就是 1 2 3 4 也写成 2 进制
  9. 1 [0 0 1]
  10. 2 [0 1 0]
  11. 3 [0 1 1]
  12. 4 [1 0 0]
  14. 依次统计每一列 1 的个数, res = XXX
  16. 1 到 4 最后一列 1 的个数是 2
  17. 2 不大于 2,所以当前位是 0, res = XX0
  19. 原数组倒数第二列 1 的个数是 3
  20. 1 到 4 倒数第二列 1 的个数是 2
  21. 3 大于 2,所以当前位是 1, res = X10
  23. 原数组倒数第三列 1 的个数是 1
  24. 1 到 4 倒数第三列 1 的个数是 1
  27. 所以 res = 010, 也就是 2

上边是重复数字的重复次数是 2 的情况，如果重复次数大于 2 的话上边的结论依旧成立。

简单的想一下，1 3 4 2 2 ，因为 2 的倒数第二位的二进制位是 1，所以原数组在倒数第二列中 1 的个数会比1 到 4 这个序列倒数第二列中 1 的个数多 1 个。如果原数组其他的数变成了 2 呢？也就2 的重复次数大于 2。

如果是 1 变成了 2，数组变成 2 3 4 2 2 ， 那么倒数第二列中 1 的个数又会增加 1。

如果是 3 变成了 2，数组变成 1 2 4 2 2 ， 那么倒数第二列中 1 的个数不会变化。

解法五

参考 -time-and-O(1)-space-without-modifying-the-array.-With-clear-explanation.) ，一个神奇的解法了。

把数组的值看成 next 指针，数组的下标看成节点的索引。因为数组中至少有两个值一样，也说明有两个节点指向同一个位置，所以一定会出现环。

举个例子，3 1 3 4 2 可以看成下图的样子。

  1. nums[0] = 3
  2. nums[3] = 4
  3. nums[4] = 2

所以我们要做的就是找到上图中有环链表的入口点 ，也就是 142 题 。

具体证明不说了，只介绍方法，感兴趣的话可以到 看一下。

我们需要快慢指针，同时从起点出发，慢指针一次走一步，快指针一次走两步，然后记录快慢指针相遇的点。

之后再用两个指针，一个指针从起点出发，一个指针从相遇点出发，当他们再次相遇的时候就是入口点了。

总

看起来比较简单的一道题，思想用了不少。经典的二分，从二进制思考问题，以及最后将问题转换的思想，都很经典。

windliang wechat

添加好友一起进步~

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 查看详情