Duplicate data in leetcode (442) array

Given a length of n Array of nums, Array nums[1,n] Duplicate elements that appear within , Please find out all that appear two The integer of , And return as an array , You must design and implement a time complexity of O(n) And only the algorithm of constant extra space is used to solve this problem .

​ Their thinking

Complexity O(n), First of all, the array can only be cycled once , And there are duplicate elements in the array , And find the repeated elements and return .

Specific implementation code example ：

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]

Copy

First of all, the above code block has realized the search for repeated numbers in the array .

But we need to analyze why the time complexity is O(n)

Explain what is Time complexity O(n)

Baidu related information explanation ,O(n) It's actually a linear first-order function , Can be seen as y = x;y With x To grow by , A specific picture will deepen my impression

In addition, there is another word that costs more brains Spatial complexity O(1)

No matter x How to change ,y Always a constant value

In time complexity O(n) How about it

We will find that n=10, The next cycle is the cycle 10 Time , If n=100, Then it will cycle 100 Time . therefore y With n Linearly varying .

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

Copy

What if it's a double-layer cycle , Then the time complexity is ​ yes O(n^2), such as

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

Copy

Because double circulation , Then the complex cycle of time is 100 Time , So the complexity is O(n^2) 了

If there is no cycle , Look for the specified element in the array , Then the complexity is O(1);

Summarize the above time complexity , There is a cycle of O(n), If there is no cycle , Find the value in the array O（1）, If it is a double-layer cycle, the time complexity is O(n^2);

Obviously, our problem uses a layer of circulation , So the complexity is O(n), We borrowed one arr = new Array(n).fill(0) In fact n The length of the array in the fast copy assignment one n A length of 0.

But we find that in the cycle , We used continue,continue stay for The function of the loop is to skip this loop , It is also the use of this , We take the current array value as arr The index of , And set a value .

About continue Skip this cycle , We can write a simple example to test

When i===2 when , Skip the current loop , Then at this time, the following result.push(i) Naturally, it will not be effective .

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

Copy

Another correspondence is break;

Obviously break Yes, stop the cycle , When i=2 when , The whole cycle is over .

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

Copy

Another analysis , In fact, we will find that , Very interesting is

By default, in the array arr It's all data 0, We use it nums[i] That is, the value of the target element is taken as arr Indexes , And it's marked 1, When there is a duplicate value next time , In fact at this time , The operation is reversed . So I won't go continue 了 , So at this time push Is to get the corresponding previous duplicate value .

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

Copy

In addition to leetcode There are also better solutions in the comment area , Specific ideas can be referred to

Reverse the corresponding subscript number , If it is already negative , That proof has appeared before , Then add this element to the array .

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

Copy