题目链接

牛客网(https://www.nowcoder.com/practice/623a5ac0ea5b4e5f95552655361ae0a8)

题目描述

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中第一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

返回描述：

如果数组中有重复的数字，函数返回true，否则返回false。

如果数组中有重复的数字，把重复的数字放到参数duplication[0]中。（ps:duplication已经初始化，可以直接赋值使用。）

Input:
{2, 3, 1, 0, 2, 5}

Output:
2

解题思路

要求时间复杂度 O(N)，空间复杂度 O(1)。因此不能使用排序的方法，也不能使用额外的标记数组。

对于这种数组元素在 [0, n-1] 范围内的问题，可以将值为 i 的元素调整到第 i 个位置上进行求解。在调整过程中，如果第 i 位置上已经有一个值为 i 的元素，就可以知道 i 值重复。

以 (2, 3, 1, 0, 2, 5) 为例，遍历到位置 4 时，该位置上的数为 2，但是第 2 个位置上已经有一个 2 的值了，因此可以知道 2 重复：

过程描述

原始数据：2,3,1,0,2,5

i=0, 判断i和nums[i]是否相等，相等就跳过，不等就继续判断nums[i]和nums[nums[i]]是否相等，不等互换位置

• 0 !== 2, 0和2换位置：1,3,2,0,2,5
• 1!=3，1和3换位置：3,1,2,0,2,5
• 3!=0，3和0换位置：0,1,2,3,2,5
• 0==0，跳过

i=1，[0,1,2,3,2,5]，i==nums[i]，跳过

i=2，[0,1,2,3,2,5]，i==nums[i]，跳过

i=3，[0,1,2,3,2,5]，i==nums[i]，跳过

i=4，[0,1,2,3,2,5]，i!=nums[i]，继续判断nums[i]【值为2】和nums[nums[i]]【值为2】，相等，就标记为找到

• 2== 2, 找到相同元素，结束

JS代码实现

function duplicate(nums, duplication) {
  if (!nums || !nums.length) {
    return false;
  }
  for(let i = 0; i < nums.length; i++) {
    while(nums[i] !== i) {
      if (nums[i] === nums[nums[i]]) {
        duplication[0] = nums[i];
        return true;
      }

      swape(nums, i, nums[i]);
    }
  }
}

function swape(nums, i, j) {
  let temp = nums[i];
  nums[i] = nums[j];
  nums[j] = temp;
}

// test code
const nums = [2, 3, 1, 0, 2, 5];
const duplication = [];
duplicate(nums, duplication);
conosle.log(duplication);