前言
又是好久没有更新了
正文
问题来源
本问题来自leetcode上的287题。
问题描述
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例 1:
输入: [1,3,4,2,2]
输出: 2
示例 2:
输入: [3,1,3,4,2]
输出: 3
分析：
先前将这题理解错了，以为是长度为n+1的数组，其中数字是从1 ~ n中每个数字都有，然后求这个重复的数字。
错误代码如下
//错误代码
func findDuplicate(nums []int) int {
l := len(nums)
ret := nums[0]
for i := 1; i < l; i++ {
ret ^= i
ret ^= nums[i]
}
return ret
}
给定一个包含 n + 1 个整数的数组 nums，要求找出其中重复的数字。一般对于链表，数组中要求找重复的数字或者节点，都可以考虑用双指针的方法来解。这里使用的是双指针中的快慢指针。一提到到快慢指针，大家就都会想到141. 环形链表的题目了。本体是否也可以转化为环形链表呢？
题目的前提说道：给定一个包含 n + 1 个整数的数组 nums，并且数组中的数字存在重复，说明nums当中的数字并不会超过nums的长度。
对于数组中的每个index，可以将其所对应的数字作为他的下一个指向的对象。
func findDuplicate(nums []int) int {
fast, slow := nums[nums[0]], nums[0]
for fast != slow {
fast, slow = nums[nums[fast]], nums[slow]
}
find := 0
for find != slow {
find, slow = nums[find], nums[slow]
}
return find
}
抽屉原理
这道题要求我们查找的数是一个整数，并且给出了这个整数的范围（在 11 和 nn 之间，包括 1 和 n），并且给出了一些限制，于是可以使用二分查找法定位在一个区间里的整数；
二分法的思路是先猜一个数（有效范围 [left, right]里的中间数 mid），然后统计原始数组中小于等于这个中间数的元素的个数 cnt，如果 cnt 严格大于 mid，（注意我加了着重号的部分「小于等于」、「严格大于」）。根据抽屉原理，重复元素就在区间 [left, mid] 里；
与绝大多数二分法问题的不同点是：正着思考是容易的，即：思考哪边区间存在重复数是容易的，因为有抽屉原理做保证。我们通过一个具体的例子来分析应该如何编写代码；
public class Solution {
public int findDuplicate(int[] nums) {
int len = nums.length;
int left = 1; //一定注意left是从1开始
int right = len - 1;
while (left < right) {
// 在 Java 里可以这么用，当 left + right 溢出的时候，无符号右移保证结果依然正确
int mid = (left + right) >>> 1;
int cnt = 0;
for (int num : nums) {
if (num <= mid) {
cnt += 1;
}
}
// 根据抽屉原理，小于等于 4 的个数如果严格大于 4 个
// 此时重复元素一定出现在 [1, 4] 区间里
if (cnt > mid) {
// 重复元素位于区间 [left, mid]
right = mid;
} else {
// if 分析正确了以后，else 搜索的区间就是 if 的反面
// [mid + 1, right]
left = mid + 1;
}
}
return left;
}
}
总结：
勤思考。
结语
不管怎么样好好加油。
