寻找重复数

问题陈述

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

常规思路

1
2
3
4
5
6
7
8
9
publiic int findDuplicate(int[] nums){
    Arrays.sort(nums);
    for(int i=0;i<nums.length-1;i++){
        if(nums[i]==nums[i+1]){
            return nums[i];
        }
    }
    return -1;
}

原地寻找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//以数组元素的值作为索引，若出现相同索引，则必定是重复值。
class Solution {
    public int findRepeatNumber(int[] nums) {
        int i = 0;
        while(i < nums.length) {
            if(nums[i] == i) {//当前值与索引相同，跳过
                i++;
                continue;
            }
            if(nums[nums[i]] == nums[i]) return nums[i];
            int tmp = nums[i];//若不等，交换至索引位置。
            nums[i] = nums[tmp];
            nums[tmp] = tmp;
        }
        return -1;//若没找到，返回-1。
    }
}

哈希表

1
2
3
4
5
6
7
8
9
10
publiic int findDuplicate(int[] nums){
    HashSet<Integer> set=new HashSet<>();
    for(int num:nums){
        if(set.contains(num)){
            return num;
        }
        set.add(num);
    }
    return -1;
}

二分法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
publiic int findDuplicate(int[] nums){
    int low = 1, high = nums.length - 1 // 数组项的范围 1 到 n
  while (low < high) { // 在循环中缩小区间，区间闭合循环结束
    int mid = (low + high) >> 1 // 求中位数
    int count = 0
    for (int i = 0; i < nums.length; i++) {
      if (nums[i] <= mid) count++ // 统计小于等于mid的个数
    }
    if (count > mid) { // 重复数落在 [1,mid]
      high = mid       // 区间收缩
    } else {           // 落在 [mid+1,n]
      low = mid + 1    // 区间收缩
    }
  }
  return low
}

快慢指针

比如，nums 数组：[4, 3, 1, 2, 2][4,3,1,2,2]
如果以 nums[0] 的值 4 作为索引，去到 nums[4]
如果以 nums[4] 的值 2 作为索引，去到 nums[2]
如果以 nums[2] 的值 1 作为索引，去到 nums[1]……
从一项到另一项，有了指向性的联系，有点像“单向链表”
形成一条链表：4 > 2 > 1 > 3 > 2 ，可见链表又指回了 2 ，“链表有环”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int findDuplicate(int[] nums) {
    int slow = nums[0];
    int fast = nums[nums[0]];
    //寻找相遇点
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[nums[fast]];
    }
    //slow 从起点出发, fast 从相遇点出发, 一次走一步
    slow = 0;
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
}