This is the 24th day of my participation in the August Text Challenge.More challenges in August

Title description:

350. Intersection of Two Arrays II – Force Buckle (LeetCode) (leetcode-cn.com)

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

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2] output: [2,2]Copy the code

Example 2:

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

Description:

  • The number of occurrences of each element in the output should be the same as the minimum number of occurrences of the element in both arrays.
  • We can ignore the order of the output.

Advanced:

  • What if the given array is already sorted? How will you optimize your algorithm?
  • If nums1 is much smaller than NUMs2, which method is better?
  • What do you do if nums2 elements are stored on disk, memory is limited, and you can’t load all elements into memory at once?

Thought analysis

Hash table

This is a bit different from the intersection of leetcode.349 arrays, where the same number can occur multiple times, and the number of occurrences in the intersection is equal to the minimum number of occurrences in both arrays.

So we need to keep an extra count of how many times each number occurs.

First, nums1 is iterated, and the frequency counts of each element

Iterate through NUMs2, add the element to the answer if it exists in the hash table, and count – 1 for that element in the hash table.

AC code

class Solution {
    fun intersect(nums1: IntArray, nums2: IntArray): IntArray {
        var counts=HashMap<Int.Int>() nums1.forEach{ counts.put(it,(counts[it]? :0) +1)}var ans=ArrayList<Int>(counts.size)
        nums2.forEach{
            if(counts[it]? :0 >0){ ans.add(it) counts.put(it,(counts[it]? :0) -1)}}return ans.toIntArray()
    }
}
Copy the code

Sort + double pointer

After sorting the two numbers, we can define two Pointers to traverse the two arrays.

If they are equal, the number is one of the intersections. If the two numbers are not equal, the pointer to the smaller number is moved to the right by one.

class Solution {
    fun intersect(nums1: IntArray, nums2: IntArray): IntArray {
        if(nums1.isEmpty() || nums2.isEmpty()){
            return IntArray(0)}var i = 0
        var j = 0
        var index = 0
        
        var resultArray = arrayListOf<Int>()

        nums1.sort()
        nums2.sort()
        
        while (i < nums1.size && j < nums2.size){
            if(nums1[i] == nums2[j]){ 
                resultArray.add(nums1[i])
                i++
                j++
                index++
            }else if(nums1[i] < nums2[j]){
                i++
            }else if(nums1[i] > nums2[j]){
                j++
            }
        }
       
        return resultArray.toIntArray()
    }
}

Copy the code

conclusion

This problem is similar to the intersection of the two arrays in Leetcode.349, except for the problem of element duplication.

reference

Intersection of two Arrays II – Intersection of two Arrays II – Force buckle (LeetCode) (leetcode-cn.com)