Question

Formatted question description: https://leetcode.ca/all/350.html

 350	Intersection of Two Arrays II

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

 Example:
 Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

 Note:
 Each element in the result should appear as many times as it shows in both arrays.
 The result can be in any order.

 Follow up:
 What if the given array is already sorted? How would you optimize your algorithm?
 What if nums1's size is small compared to nums2's size? Which algorithm is better?
 What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

 @tag-array

Algorithm

HashSet

The previous expansion of 349 Intersection of Two Arrays, the difference is that this question allows to return repeated numbers, and returns as many as possible.

HashMap to establish the mapping between the characters in nums1 and the number of occurrences, and then traverse the nums2 array.

If the number of the current character in the HashMap is greater than 0, add this character to the result, and then the corresponding value of the HashMap will be decremented by 1.

Two pointers

Sort the two arrays first, and then use two pointers to point to the starting positions of the two arrays,

  • If the numbers pointed to by the two pointers are equal, it is stored in the result, and both pointers are incremented by 1,
  • If the number pointed to by the first pointer is large, the second pointer is incremented by 1, and vice versa

Code

Java

  • import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.HashMap;
    
    public class Intersection_of_Two_Arrays_II {
    
        class Solution_sorted {
            public int[] intersect(int[] nums1, int[] nums2) {
    
                Arrays.sort(nums1);
                Arrays.sort(nums2);
    
                int p1 = 0;
                int p2 = 0;
    
                ArrayList<Integer> list = new ArrayList<>();
    
                while (p1 < nums1.length && p2 < nums2.length) {
                    int val1 = nums1[p1];
                    int val2 = nums2[p2];
    
                    if (val1 == val2) {
                        list.add(val1);
                        p1++;
                        p2++;
                    } else if (val1 < val2) {
                        p1++;
                    } else {
                        p2++;
                    }
                }
    
    //            int[] result = new int[list.size()];
    //            int i = 0;
    //            while (i < list.size()){
    //                result[i] = list.get(i);
    //                i++;
    //            }
    
                int[] result = list.stream().mapToInt(Integer::intValue).toArray();
    
                return result;
    
            }
        }
    
        class Solution {
            public int[] intersect(int[] nums1, int[] nums2) {
    
                // from number to its appearance count
                HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
    
                // time: O(N), space: O(N)
                for(int i: nums1){
                    if(hm.containsKey(i)) {
                        hm.put(i, hm.get(i)+1);
                    } else {
                        hm.put(i, 1);
                    }
                }
    
                ArrayList<Integer> list = new ArrayList<Integer>();
                for(int i: nums2){
                    if(hm.containsKey(i)) {
                        if(hm.get(i)>1){
                            hm.put(i, hm.get(i)-1);
                        } else{
                            hm.remove(i);
                        }
    
                        list.add(i);
                    }
                }
    
                int[] result = list.stream().mapToInt(Integer::intValue).toArray();
    
                return result;
            }
        }
    }
    
  • class Solution {
    public:
        vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
            vector<int> res;
            int i = 0, j = 0;
            sort(nums1.begin(), nums1.end());
            sort(nums2.begin(), nums2.end());
            while (i < nums1.size() && j < nums2.size()) {
                if (nums1[i] == nums2[j]) {
                    res.push_back(nums1[i]);
                    ++i; ++j;
                } else if (nums1[i] > nums2[j]) {
                    ++j;
                } else {
                    ++i;
                }
            }
            return res;
        }
    };
    
  • class Solution(object):
      def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        ans = []
        nums1.sort()
        nums2.sort()
        i = j = 0
        while i < len(nums1) and j < len(nums2):
          if nums1[i] < nums2[j]:
            i += 1
          elif nums1[i] > nums2[j]:
            j += 1
          else:
            ans.append(nums1[i])
            i += 1
            j += 1
    
        return ans
    
    

All Problems

All Solutions