https://leetcode-cn.com/problems/find-the-duplicate-number/

快慢指针

注意题目限制

image.png
image.png
其实这道题就是有环链表怎么找到第一个入环节点…..

结论： 快指针一次走两步，慢指针一次走一步，第一次他俩相遇后，快指针回到原点，慢指针不动，接着快指针变成一次走一步，慢指针也是一次走一步，等到再次相遇时就是第一个入环节点

  1. public int findDuplicate(int[] nums) {
  2.  if (nums == null || nums.length < 2) {
  3.             return -1;
  4.         }
  5.         int slow = nums[0];
  6.         int fast = nums[nums[0]];
  7.         while (slow != fast) {
  8.             slow = nums[slow];
  9.             fast = nums[nums[fast]];
  10.         }
  11.         fast = 0;
  12.         while (slow != fast) {
  13.             fast = nums[fast];
  14.             slow = nums[slow];
  15.         }
  16.         return slow;
  17.     }

位运算

  1.     // 法二：位运算
  2.     public int findDuplicate2(int[] nums) {
  3.         if (nums == null || nums.length < 2) {
  4.             return -1;
  5.         }
  6.         int x1 = 0;
  7.         for (int i = 1; i < nums.length; i++) {
  8.             x1 ^= i;
  9.         }
  10.         for (int num : nums) {
  11.             x1 ^= num;
  12.         }
  13.         return x1;
  14.     }