Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/350.html
Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.
Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2,2]
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [4,9] Explanation: [9,4] is also accepted.
Constraints:
1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 1000
Follow up:
- What if the given array is already sorted? How would you optimize your algorithm?
- What if
nums1's size is small compared tonums2's size? Which algorithm is better? - What if elements of
nums2are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?
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
-
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 int[] intersect(int[] nums1, int[] nums2) { Map<Integer, Integer> counter = new HashMap<>(); for (int num : nums1) { counter.put(num, counter.getOrDefault(num, 0) + 1); } List<Integer> t = new ArrayList<>(); for (int num : nums2) { if (counter.getOrDefault(num, 0) > 0) { t.add(num); counter.put(num, counter.get(num) - 1); } } int[] res = new int[t.size()]; for (int i = 0; i < res.length; ++i) { res[i] = t.get(i); } return res; } } -
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: def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]: counter = Counter(nums1) res = [] for num in nums2: if counter[num] > 0: res.append(num) counter[num] -= 1 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 -
func intersect(nums1 []int, nums2 []int) []int { counter := make(map[int]int) for _, num := range nums1 { counter[num]++ } var res []int for _, num := range nums2 { if counter[num] > 0 { counter[num]-- res = append(res, num) } } return res } -
function intersect(nums1: number[], nums2: number[]): number[] { const map = new Map<number, number>(); for (const num of nums1) { map.set(num, (map.get(num) ?? 0) + 1); } const res = []; for (const num of nums2) { if (map.has(num) && map.get(num) !== 0) { res.push(num); map.set(num, map.get(num) - 1); } } return res; } -
/** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number[]} */ var intersect = function (nums1, nums2) { const counter = {}; for (const num of nums1) { counter[num] = (counter[num] || 0) + 1; } let res = []; for (const num of nums2) { if (counter[num] > 0) { res.push(num); counter[num] -= 1; } } return res; }; -
use std::collections::HashMap; impl Solution { pub fn intersect(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> { let mut map = HashMap::new(); for num in nums1.iter() { *map.entry(num).or_insert(0) += 1; } let mut res = vec![]; for num in nums2.iter() { if map.contains_key(num) && map.get(num).unwrap() != &0 { map.insert(num, map.get(&num).unwrap() - 1); res.push(*num); } } res } } -
class Solution { /** * @param Integer[] $nums1 * @param Integer[] $nums2 * @return Integer[] */ function intersect($nums1, $nums2) { $rs = []; for ($i = 0; $i < count($nums1); $i++) { $hashtable[$nums1[$i]] += 1; } for ($j = 0; $j < count($nums2); $j++) { if (isset($hashtable[$nums2[$j]]) && $hashtable[$nums2[$j]] > 0) { array_push($rs, $nums2[$j]); $hashtable[$nums2[$j]] -= 1; } } return $rs; } }