Skip to content

Latest commit

 

History

History
87 lines (71 loc) · 2.95 KB

README.md

File metadata and controls

87 lines (71 loc) · 2.95 KB

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

Companies:
Amazon, Facebook, Bloomberg, Apple, LinkedIn, VMware

Related Topics:
Array, Hash Table, Two Pointers, Binary Search, Sorting

Similar Questions:

Solution 1. Hash Set

// OJ: https://leetcode.com/problems/intersection-of-two-arrays/
// Author: github.com/lzl124631x
// 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;
    }
};

Solution 2. Sort + Two Pointers

If both arrays are already sorted, this algorithm would just take O(A + B) time.

// OJ: https://leetcode.com/problems/intersection-of-two-arrays/
// Author: github.com/lzl124631x
// Time: O(AlogA + BlogB)
// Space: O(1)
class Solution {
public:
    vector<int> intersection(vector<int>& A, vector<int>& B) {
        sort(begin(A), end(A));
        sort(begin(B), end(B));
        vector<int> ans;
        int i = 0, j = 0, M = A.size(), N = B.size();
        while (i < M && j < N) {
            if (A[i] < B[j]) ++i;
            else if (A[i] > B[j]) ++j;
            else {
                int n = A[i];
                while (i < M && A[i] == n) ++i;
                while (j < N && B[j] == n) ++j;
                ans.push_back(n);
            }
        }
        return ans;
    }
};