287. 寻找重复数

leetcode
,

题目

这里要注意，假设了只有一个重复整数，大概就是[1,2,3,4,4]/[1,2,2,3,4]/[2,2,2,2]这样，然后可能是乱序的。
image.png

思路一 排序

排序之后重复的元素肯定是连在一起的，遍历然后保存上一个遍历的元素判断是否重复即可

1
2
3
4
5
6
7
8
function findDuplicate(nums) {
  nums.sort((a, b) => (a - b));
  let last = nums[0];
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] == last) return nums[i];
    else last = nums[i];
  }
}

思路二 出现次数

哈希表记录

虽然LeetCode上可运行，但这个应该是不符合O(1)的空间复杂度的

1
2
3
4
5
6
7
var findDuplicate = function(nums) {
  let map = {}
  for(let val of nums){
      if(map[val]) return val;
      else map[val] = true;
  }
};

利用数据特性

以上数据有一个特性，比如输入的[1,3,4,2,2]，总结出下表

元素 count
1 1
2 3
3 4
4 5

其中出现的元素有1,2,3,4，count则代表小于等于该元素的元素个数，比如小于等于1的元素只有1（1个），小于等于2的元素有1,2,2（3个）。由于整数的范围是[1,n]，所以只要出现了元素，count就等于元素数值，出现了重复元素count就会大于元素数值，又由于题目给出数据只存在一个重复多次的元素，那么只要找到第一个count>元素数值的元素即可。

普通遍历

1
2
3
4
5
6
7
8
9
10
11
function findDuplicate(nums) {
  for (let i = 1; i < nums.length; i++) {
    let count = 0;
    for (let val of nums) {
      if (i >= val) count += 1;
    }
    if (count > i) {
      return i
    }
  }
}

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function findDuplicate(nums) {
  let l = 1, r = nums.length - 1, ans = -1;
  while (l <= r) {
    let mid = (l + r) >> 1
    let count = 0
    for (let val of nums) {
      if (val <= mid) count += 1;
    }
    if (count > mid) {
      ans = mid;
      r = mid - 1;
    } else {
      l = mid + 1;
    }
  }
  return ans;
}

快慢指针

由于存在的重复的数字 target，因此 target 这个位置一定有起码两条指向它的边，因此整张图一定存在环，且我们要找到的 target 就是这个环的入口。

我们先设置慢指针 slow 和快指针 fast ，慢指针每次走一步，快指针每次走两步，直到两个指针相遇，此时我们再将 slow 设为 0，两个指针每次移动一步，再次相遇的点就是答案。

这里简单解释为什么后面将 slow 放置起点后移动相遇的点就一定是答案了。如图：

image.png
假设起点到环入口距离为a，环长为L，相遇点到环入口为b，环剩余部分为c，则有则慢指针走了a+c，快指针走了a+c+kL，其中k是圈数未知。由于慢指针走一步，快指针走两步，快指针走的距离也可以为2(a+c)，得出等式 2(a+c) = a+c+kL。解得 a = kL - c, 倒退一圈可以变成a= (k-1)L + (b+c) -c,化简可得a=(k-1)L+b,很明显如果慢指针从0开始走到环入口（a）,快指针同时一步一步移动，会走k-1圈，并多走b步到达环入口，而环入口则是我们重复的元素，即可得出答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
function findDuplicate(nums) {
  let slow = fast = 0;
  do {
    slow = nums[slow];
    fast = nums[nums[fast]];
  } while (slow != fast)
  slow = 0;
  while (slow != fast) {
    slow = nums[slow];
    fast = nums[fast];
  }
  return slow;
}