P157 查找重复数字

描述#

这个题目说的是，给你一个大小为 n+1 的整数数组，数组中的数字都大于等于 1 并且小于等于 n。尝试证明数组中至少存在一个重复的数字。假设数组中只存在一个重复的数字，你要找出这个数字。

题目要求不能修改原数组，并且只能使用 O(1) 的辅助空间。

比如说，给你的数组是：
4, 3, 4, 1, 2, 5
这个数组的大小为 6，也就是说数组中每个数字都大于等于 1 并且小于等于 5。数组中重复的数字为 4，于是你要返回 4。
再比如说，给你的数组是：
1, 3, 3, 3
这个数组的大小为 4，也就是说数组中每个数字都大于等于 1 并且小于等于 3。数组中重复的数字是 3，于是你要返回 3。

代码#

public class AlgoCasts {

  // Time: O(n^2), Space: O(1)
  public int findDuplicateBruteForce(int[] nums) {
    for (int i = 0; i < nums.length; ++i)
      for (int j = i+1; j < nums.length; ++j)
        if (nums[i] == nums[j])
          return nums[i];
    return -1;
  }

  // Time: O(n*log(n)), Space: O(1)
  public int findDuplicateBinarySearch(int[] nums) {
    int low = 1, high = nums.length - 1;
    while (low < high) {
      int mid = low + (high - low) / 2;
      int count = 0;
      for (int num: nums)
        if (num <= mid)
          ++count;
      if (count > mid) high = mid;
      else low = mid + 1;
    }
    return low;
  }

  // Time: O(n), Space: O(1)
  public int findDuplicateTwoPointer(int[] nums) {
    int slow = nums[0];
    int fast = nums[nums[0]];
    while (slow != fast) {
      slow = nums[slow];
      fast = nums[nums[fast]];
    }

    int p = 0;
    while (slow != p) {
      slow = nums[slow];
      p = nums[p];
    }
    return slow;
  }

}