“This is the 22nd day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

Hi, everybody. I’m handsome.

Today to solve the intersection of two arrays, continue to consolidate through the actual topic, play hash table!

LeetCode 349: Intersection of two arrays

The question

Given two arrays, calculate their intersection.

The sample

Input: nums1 = [4, 9, 5], nums2 = [9, 4, 9, 8, 4]

Output: [9, 4]

prompt

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

title

Water problem, the difficulty is simple.

Find the intersection of two arrays (nums2, nums1).

Each element in the output must be unique.

Why can we hash this problem?

I mentioned earlier in LeetCode202 Happy Numbers: To find a number in a pile of numbers, of course, is to throw the hash, after all, is the second man in the search, the time complexity is O(1).

This problem has something in common with the happiness number: it also doesn’t limit the size of the number, so you can’t use arrays as hash tables.

In cases where the size of a value is currently unknown, we can use the set set.

Using a set is great, but I recommend not using library functions directly here.

We use the programming language may not be the same, it is best to use the programming language with the data structure to simulate, after all, for beginners, or have to do step by step.

The illustration

For example, nums1 = [4, 9, 5] and nums2 = [9, 4, 9, 8, 4].

First initialize a hash table and a list of results.

Hash = {} hash = []Copy the code

The first step is to iterate over nums1 and store the numbers that appear in the hash table.

Add the first element of nums1 to the hash table with the corresponding value set to 1.

For I in nums1: if not hash. Get (I): hash[I] = 1Copy the code

Since each element in the output must be unique, it doesn’t matter what the value of the key is, so in this case, I set the value to 1 no matter how many times an element appears in the array.

After iterating through nums1, the hash table looks like the following:

The second step is to traverse the NUMs2 array. If the elements in the NUMs2 array appear in the hash table, they are proved to be the elements that intersect the NUMs1 array and are added to the result list.

In the nums2 array, the first element is 9. In the hash table, element 9 is added to the result list and set to 0.

For j in nums2: if hash. Get (j): res.append(j) hash[j] = 0Copy the code

After similarly iterating through NUMs2, the final result is as follows:

Res is the end result.

In this problem, nums1 and NUMs2 arrays are solved and traversed, so the time complexity is O(n + m), where n and M are the lengths of two arrays respectively.

An additional hash table is built, so the space complexity is O(Max (n, m)).

Code implementation

Python code implementation

class Solution: def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: If not nums1 or not nums2: Return [] # initializes the hash table hash = {} # initialization list of results, store the result res = [] # key to hash table nums1 number in the array, the value for value for I nums1 in: If not hash. Get (I) : the hash [I] traversal nums = 1 #, if number of nums2 array appeared in the hash table, the corresponding number in the list of results, the corresponding value value set - 0 for j nums2 in: if hash.get(j): res.append(j) hash[j] = 0 return resCopy the code

Java code implementation

import java.util.HashSet; import java.util.Set; class Solution { public int[] intersection(int[] nums1, int[] nums2) { if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) { return new int[0]; } Set<Integer> set1 = new HashSet<>(); Set<Integer> resSet = new HashSet<>(); Nums1 for (int I: nums1) {set1.add(I); For (int I: nums2) {if (set1.contains(I)) {resset.add (I); } } int[] resArr = new int[resSet.size()]; int index = 0; for (int i : resSet) { resArr[index++] = i; } return resArr; }}Copy the code

Diagram the intersection of two arrays ends here.

This is hash 4, I don’t know if you notice my little idea:

Question 1 [LeetCode242 valid letter heterotopic] and question 2 [LeetCode383 ransom note], question 3 [LeetCode202 happiness number] and the intersection of two arrays are the same type of problem.

Repeat the same type of problem many times, and you will find that in the end, what you remember in your mind is not the code to implement the problem, but the way to solve the problem.

When something like “I’ve seen it before, I know how to do it this way” comes along, bitches are ready to kick in.

Come on, everybody! And give me a thumbs up, too.

I’m Handsome. See you next time!