Leo Lei | 雷雨
Oct 21, 2018
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]
Brute force would cost O(N2). A better way would be sorting the longer list, and binary search the unique items of the short list in the sorted list.
Time: NlogM, where M is the length of the longer list, N is the unique items in the shorter list.
Python has a bisect module implementing the binary search algorithm. However, it doesn't have a method checking
the existence of a particular value. Some workaround is needed.
class Solution:
def intersection(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
M, N = len(nums1), len(nums2)
if M < N:
return self.intersection(nums2, nums1)
nums1.sort()
ans = []
for num in set(nums2):
i = bisect.bisect_left(nums1, num)
if i != M and nums1[i] == num:
ans.append(num)
return ans
pygtrie: a Python library implementing a trie data structure offered by Google.
So far Python hasn't provided a standard library for any tree-kind data structures, e.g. there is no Java's TreeMap equivalent in Python.
Trie data structure, also known as radix or prefix tree, is a tree associating keys to values where all the descendants of a node have a common prefix (associated with that node).
The trie module contains Trie, CharTrie and StringTrie classes each implementing a mutable mapping interface, i.e. dict interface. As such, in most circumstances, Trie could be used as a drop-in replacement for a dict, but the prefix nature of the data structure is trie’s real strength.
Features
- A full mutable mapping implementation.
- Supports iterating over as well as deleting a subtrie.
- Supports prefix checking as well as shortest and longest prefix look-up.
- Extensible for any kind of user-defined keys.
- A PrefixSet supports “all keys starting with given prefix” logic.
- Can store any value including None.
None