LeetCode #349 Intersection of Two Arrays
Problem
Given two arrays, write a function to compute their intersection.
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]Note:
- Each element in the result must be unique.
- The result can be in any order.
Solution — Hash Set
Compact nums1 and nums2 to be two hash sets and iterate one to check if elements are in another one.
Complexity
It takes O(m + n) time to build two hash sets if m and n denote to counts of numbers of two given lists. And it takes O(mn) average time to check if elements in one are also in another one. Furthermore, without loss generality, it need O(mn*logn) time because search operation of hash set will be O(logn) in worst case. Therefore, its time complexity will be O(m + n + mn)/O(m + n + mn*logn) = O(mn)/O(mn*logn) in average/worst cases.
It’s trivial that it needs O(m+n) extra space for these two hash sets.
Solution — Binary Search
We can sort the list which has less elements and iterate another list to check if elements are in the sorted list.
Complexity
Without loss of generality, assume n is counts of numbers of the list with less elements and m is counts of numbers of another one. It takes O(nlogn) time for sorting and take O(mlogn) or O(m(logm)(logn)) time (average or worst cases) to filter and compact result into a set. Thus, its time complexity is O((n+m)*logn)/O((n+mlogm)*logn) = O(mlogn)/O(m(logm)(logn)) in average/worst cases.
For space complexity, it uses O(m) extra space for saving result.
