给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例 1:
输入: [1,3,4,2,2]
输出: 2
示例 2:
输入: [3,1,3,4,2]
输出: 3
我们注意看下题目，题目明确说明了数组 nums 包含 1 和 n
，并且只有一个重复的整数，如果不考虑说明中的第四点的话这段代码是正确的。解释一下原理。a
从 1 一直异或到 n，其中有一个重复的数字 x ，那么就是
1 ^ 2 ^ 3 ··· ^ x ^ x ^ ··· ^ n。异或操作因为是半加运算，因此是满足交换律的，我们把 x 拿到最后面， 即
1 ^ 2 ^ 3 ··· ^ n ^ x ^ x，而 x ^ x 一定是 0 ，因此 1 ~ n
每个数异或了 2 次，而 x 异或了 3 次，所以最后 res 的值就是我们要找的 x
的值。
// 这里我们不考虑第四点的时候做的答案，在此只是说明一下用异或的方法来解决一些特殊的问题 public int FindDuplicate(int[] nums) { int res = 0; for(int i = 0; i < nums.Length; i++){ res ^= nums[i]; res ^= i; } return res; }
但是有了第四点，这个方法就不太好用了，下面是一个正确的解法，由于跟异或没有太多的关系，因此就不过多解释。
// 这是正确答案，如果觉得不好理解可以把这个数组当做一个存在环的单链表，利用快慢指针法来寻找链表的环 public int FindDuplicate(int[] nums){ if(nums.Length > 1){ int slow = nums[0]; int fast = nums[nums[0]]; while(slow != fast){ slow = nums[slow]; fast = nums[nums[fast]]; } fast = 0; while(fast != slow){ fast = nums[fast]; slow = nums[slow]; } return slow; } return -1; }
今天的文章分享就到这里了，希望对大家的学习和工作有所帮助哦~