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<n;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;
};

复制