leetcode:442 数组中重复的数据

给定一个长度为 n 的数组nums，数组nums[1,n]内出现的重复的元素，请你找出所有出现两次的整数，并以数组形式返,你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。

解题思路

复杂度 O(n),首先肯定只能循环一次数组，且数组中有重复的元素，并且找出重复的元素并返回。

具体实现代码示例：

var findDuplicates = (nums) => {
  const result = [];
  const arr = new Array(nums.length).fill(0);
  for (let i = 0; i < arr.length; i++) {
    if (!arr[nums[i]]) {
      arr[nums[i]] = 1;
      continue;
    }
    result.push(nums[i]);
  }
  return result;
};
const res = findDuplicates([4, 3, 2, 7, 8, 2, 3, 1]);
console.log(res); // [2,3]

首先以上代码块已经实现了寻找数组中的重复数字了。

但是我们要具体分析下时间复杂度为什么是 O(n)

解释一下什么是时间复杂度O(n)

百度相关资料解释，O(n)实际上是一个线性的一次函数，可以看成 y = x;y 随着 x 的增长而增长,具体一张图加深下印象

另外还有一个比较费脑壳的词空间复杂度O(1)

不管x怎么变化，y始终是一个定值

在时间复杂度 O(n)具体是怎么样

我们会发现 n=10,下面循环就循环的 10 次，如果 n=100,那么就会循环 100 次。，所以y是随着n呈线性变化的。

var n = 10;
var y = 0;
for (let x = 0; x < n; x++) {
  console.log(x);
  y += x;
}

如果是双层循环呢，那么此时时间复杂度就是 O(n^2),比如

var n = 10;
for (let i = 0; i < n; i++) {
  for (let j = 0; j < b; j++) {
    console.log(j);
  }
}

因为双层循环，那么时间复杂循环就是 100 次了，所以复杂度就 O(n^2)了

如果没有循环，在数组中寻找指定元素呢，那么复杂度就 O(1);

总结以上时间复杂度，有一层循环就是O(n),如果没有循环，在数组中找值O（1），如果是双层循环那么时间复杂度就是O(n^2)；

很显然我们这道题使用的是一层循环，那么复杂度就是 O(n),我们借用了一个arr = new Array(n).fill(0)其实是在n长度的数组中快速拷贝赋值一n个长度的 0。

但是我们发现在循环中，我们使用了continue,continue在for循环的作用是跳过本次循环，也正是利用这一点，我们将当下数组值作为arr的索引，并设置一个值。

关于continue跳过本次循环，我们可以写个简单的例子测试一下

当i===2时，跳过当前循环，那么此时后面的result.push(i)自然就不会有效了。

const result = [];
for (let i = 0; i < 5; i++) {
  if (i === 2) {
    continue;
  }
  result.push(i);
}
console.log(result); // [0,1,3,4]

另外一个对应就是break;

很显然break是中止循环，当i=2时，整个循环就结束了。

const result = [];
for (let i = 0; i < 5; i++) {
  if (i === 2) {
    break;
  }
  result.push(i);
}
console.log(result); // [0,1]

再来分析，其实我们会发现，很有意思就是

默认情况数组中arr所有数据都是 0,我们用nums[i]也就是目标元素的值作为arr索引,并且标记为 1,当下次有重复的值时，其实此时，就取反操作了。所以就不会走continue了，那么此时push就是获取对应之前的重复值了。

...
if (!arr[nums[i]]) {
    arr[nums[i]] = 1;
    continue;
  }
  result.push(nums[i]);

另外在leetcode评论区里也有比较好的解法，具体思想可以参考下

给对应下标数字取反，如果已经时负数，那证明之前出现过了，那么就将该元素添加到数组中去。

function findDuplicates(nums) {
  let result = [];
  for (let i = 0; i < nums.length; i++) {
    let num = Math.abs(nums[i]);
    if (nums[num - 1] > 0) {
      nums[num - 1] *= -1;
    } else {
      result.push(num);
    }
  }
  return result;
}