Skip to content

数据中重复的数据 #36

Open
Open

Description

@maicFir

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

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions