This is the 31st day of my participation in the August Text Challenge.More challenges in August

Intersection of two arrays (Item 349)

The title

Given two arrays, write a function to calculate their intersection.

Example 1:

Enter: nums1 = [1.2.2.1], nums2 = [2.2] output: [2]
Copy the code

Example 2:

Enter: nums1 = [4.9.5], nums2 = [9.4.9.8.4] output: [9.4]
Copy the code

Description:

  • Each element in the output must be unique.
  • We can ignore the order of the output.

link

Leetcode-cn.com/problems/in…

explain

This one, this one is a classic Jane.

The solution is not so difficult, but it takes a lot of work to make it perfect.

It is easy to understand the meaning of the question. It is ok to take the intersection.

  • Each element in the output must be unique.

How do you say this is unique? There are actually two solutions:

  1. Unduplicate the two arrays so that no double digits can occur
  2. The result is de-duplicated, and each time a new element is inserted, the number is determined to be present in the answer. If it is present, the number is not processed, and the number is not advanced

In fact, I feel that the scheme will be better for a while, because the number of cycles will be correspondingly reduced after the two original arrays are reloaded, and there will be less processing to do, and you can use Set to reweight, in one step

Then there is the problem of how best to solve the size problem of two arrays.

Because to find the intersection, you must first loop through the short array, get each element in the long array after the search, if there is a push into the result, if not GG

If you loop through the long array first, you will lose some loop times, so it is necessary to loop through the short array first

One way to find the short array first is very simple. At the beginning of the function, check whether the length of argument 1 is longer than that of argument 2. If it is longer, then make a recursive call and replace the two arguments in one step

The first argument to the function is always the one with the shorter length

This kind of method everybody should be able to think out, that have a bit better plan?

Apparently there is.

Double Pointers are a good choice. First, sort the two native arrays, and then give each array a pointer, starting at 0, and incrementing gradually. If both Pointers point to the same element, push it into the result and judge the result

Here’s the second way to keep it unique, check if it’s there before you push, if it’s there, do nothing, if it’s not there, push in, and you can also use Set, which is a little bit more convenient.

If the two Pointers point to different elements, move the smaller pointer forward, because the array is sorted, so it gets bigger and bigger, and so on until the entire array is gone

So when you get to the end of a pointer you get to the end of a pointer, it makes sense to have a double pointer.

Your own answer (violence)

In fact, it can’t be called violence, just the normal answer.

var intersection = function(nums1, nums2) {
  if (nums1.length > nums2.length) {
    return intersection(nums2, nums1)
  }
  nums1 = new Set(nums1)
  nums2 = new Set(nums2)
  const res = []
  for (const num of nums1) {
    if (nums2.has(num)) {
      res.push(num)
    }
  }
  return res
};
Copy the code

Use Set to deduplicate the array, then start looping from the short array, and get the answer very smoothly

A better way (two-pointer)

var intersection = function(nums1, nums2) {
  nums1.sort((a, b) = > a - b)
  nums2.sort((a, b) = > a - b)
  const len1 = nums1.length
  const len2 = nums2.length
  let index1 = 0
  let index2 = 0
  const res = new Set(a)while (index1 < len1 && index2 < len2) {
    const num1 = nums1[index1]
    const num2 = nums2[index2]
    if (num1 === num2) {
      if(! res.has(num1)) res.add(num1) index1++ index2++ }else if (num1 < num2) {
      index1++
    } else {
      index2++
    }
  }
  return Array.from(res)
};
Copy the code

Sort the array, sort it

And then we get the length of two arrays, because the while is going to read it multiple times, so it’s better to get it out

Let’s get two Pointers, both of which start with 0, which is the first element of the array

After the preparation work is done, start to move the pointer, get two Pointers to the elements, first determine whether they are equal, if they are equal to determine whether to push into the result, if not equal to move the smaller pointer, done

Finally convert the Set into an array to return, So easy!





PS: To view previous articles and titles, click on the links below:

Here are the categories by date 👇

Front end Brush – Table of Contents (date category)

After some friends remind, the feeling should also be classified according to the question type here is classified according to the question type 👇

Front End Brush problem path – Table of Contents (Question type classification)