Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/349.html
Given two integer arrays nums1
and nums2
, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.
Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2]
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [9,4] Explanation: [4,9] is also accepted.
Constraints:
1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000
Algorithm
Use a HashSet
to put all nums1
in, and then traverse the elements of nums2
. If it exists in the HashSet, it means that it is the intersection part, add it to the HashSet of the result, and finally convert the result to the form of a vector.
Or, use two pointers
to do it, first sort the two arrays, then use the two pointers to point to the beginning of the two arrays respectively, then compare the size of the two arrays, move the pointer of the small number backward, if the two pointers point to The numbers are equal, add this number to the result.
Code
-
import java.util.Arrays; import java.util.HashSet; import java.util.Set; public class Intersection_of_Two_Arrays { // Sort both arrays, use two pointers // Time complexity: O(nlogn) public class Solution { public int[] intersection(int[] nums1, int[] nums2) { Set<Integer> set = new HashSet<>(); Arrays.sort(nums1); Arrays.sort(nums2); int i = 0; int j = 0; while (i < nums1.length && j < nums2.length) { if (nums1[i] < nums2[j]) { i++; } else if (nums1[i] > nums2[j]) { j++; } else { set.add(nums1[i]); i++; j++; } } int[] result = new int[set.size()]; int k = 0; for (Integer num : set) { result[k++] = num; } return result; } } // Use two hash sets // Time complexity: O(n) public class Solution_hashset { public int[] intersection(int[] nums1, int[] nums2) { Set<Integer> set = new HashSet<>(); Set<Integer> intersect = new HashSet<>(); for (int i = 0; i < nums1.length; i++) { set.add(nums1[i]); } for (int i = 0; i < nums2.length; i++) { if (set.contains(nums2[i])) { intersect.add(nums2[i]); } } int[] result = new int[intersect.size()]; int i = 0; for (Integer num : intersect) { result[i++] = num; } return result; } } } ############ class Solution { public int[] intersection(int[] nums1, int[] nums2) { Set<Integer> s = new HashSet<>(); for (int num : nums1) { s.add(num); } Set<Integer> t = new HashSet<>(); for (int num : nums2) { if (s.contains(num)) { t.add(num); } } int[] res = new int[t.size()]; int i = 0; for (int num : t) { res[i++] = num; } return res; } }
-
// OJ: https://leetcode.com/problems/intersection-of-two-arrays/ // Time: O(A + B) // Space: O(A + B) class Solution { public: vector<int> intersection(vector<int>& A, vector<int>& B) { unordered_set<int> a(begin(A), end(A)), b(begin(B), end(B)); vector<int> ans; for (int n : a) { if (b.count(n)) ans.push_back(n); } return ans; } };
-
''' https://docs.python.org/3/reference/expressions.html#operator-precedence high to low: ** *, @, /, //, % +, - <<, >> & ^ | in, not in, is, is not, <, <=, >, >=, !=, == and or if – else ''' class Solution: def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: s = set(nums1) res = set() for num in nums2: if num in s: res.add(num) return list(res) # no extra space class Solution: def intersection(self, nums1: List[int], nums2: List[int]) -> 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]) # for Leetcode 350, input with duplicates if (not ans) or (len(ans) > 0 and ans[-1] != nums1[i]): ans.append(nums1[i]) i += 1 j += 1 return ans ############ class Solution(object): def intersection(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: List[int] """ d = {} ans = [] for num in nums1: d[num] = d.get(num, 0) + 1 for num in nums2: if num in d: ans.append(num) del d[num] return ans
-
func intersection(nums1 []int, nums2 []int) []int { s := make(map[int]bool) for _, num := range nums1 { s[num] = true } t := make(map[int]bool) var res []int for _, num := range nums2 { if s[num] && !t[num] { res = append(res, num) t[num] = true } } return res }
-
/** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number[]} */ var intersection = function (nums1, nums2) { const s = new Set(); for (const num of nums1) { s.add(num); } let res = new Set(); for (const num of nums2) { if (s.has(num)) { res.add(num); } } return [...res]; };
-
class Solution { /** * @param Integer[] $nums1 * @param Integer[] $nums2 * @return Integer[] */ function intersection($nums1, $nums2) { $rs = []; $set1 = array_values(array_unique($nums1)); $set2 = array_values(array_unique($nums2)); for ($i = 0; $i < count($set1); $i++) { $hashmap[$set1[$i]] = 1; } for ($j = 0; $j < count($set2); $j++) { if ($hashmap[$set2[$j]]) array_push($rs, $set2[$j]); } return $rs; } }