HashTable
Dictionary, Set, 例题
底层机制
set是简化版hashtable，而hashtable的本质其实是array（或者说Python里的list），因为list的本质就是array index和value的映射。所以关键问题是把key转换成index。一般分成3步：
通过key和hash function计算它的hash_number=hash(key) 这一步虽然可能有collision但是可能性比较低
index=hash_number%N, N是array size。 这一步有很大概率有collision，取决于N的大小
如果有hash collision，两种方法来解决（正文）； 如果没有，list[index]=value
Dictionary 使用场景
TF-IDF (Term Frequency- Inverse Document Frequency) 统计词频时，可以用list来统计频率，但是使用list的缺点是每次更新频率的时间复杂度都是O(n), 只能遍历一遍、找到词、给词频+1； 随着单词变多，这个过程就变得低效了。
在Python中，可以使用dictionary的结构来实现高效的“更新词频“的需求。
def words_to_frequencies (words):
myDict={}
for word in words:
if word in myDict:
myDict[word]+=1
else:
myDict[word]=1
return myDictTime Complexity: O(n)
Space Complexity: O(1) 如果我们不算return值的话，那没有额外空间的消耗
Example: 查找高频
如果要找到频率最高的word，分两步1. 遍历，找到最大的值； 2. 找到list，返回
def most_common_words (freqs):
best = max(freqs.values())
words = [
key #代表元 expression
for key, val in freqs.items() #for循环
if val==best #判断条件
]
return (words, best) List comprehension的写法：[expression for elem in collection if condition]
相类似的字典也有dictionary comprehension，只需要把[] 换成{}
{key_expression: value_expression for value in collection if condition}
Example：合并大小写的频次
mydic = {'a': 10, 'b': 6, 'A': , 'B': }
new_mydic={
k.lower(): mydict.get(k.lower(), 0) + mydic.get(k.upper(),0)
for k in mydic.keys()
}
#output: {'a': 17, 'b': 34, 'z': 3}get():
Python 字典(Dictionary) get() 函数返回指定key的value，如果值不在字典中返回默认值。
语法
dict.get(key, default=None)参数
key -- 字典中要查找的键。
default -- 如果指定键的值不存在时，返回该默认值。
返回值
返回指定键的值，如果值不在字典中返回默认值None。
实例
dict = {'Name': 'Zara', 'Age': 27}
print "Value : %s" % dict.get('Age')
print "Value : %s" % dict.get('Sex', "Never")以上实例输出结果为：
Value : 27
Value : Never第一步：先把词频算出来
第二步：sorting，按照单词的频率排序，而且是频率加负号，按负的频率排序，频率越大顺序越小。 或者也可以用key = lambda kv: kv[1], reverse=True
sorted的syntax: sorted(iterable, key=key, reverse=reverse)
再次注意，dictionary没有顺序！所以不能直接输出前x个。
class Solution(object):
def topKFrequent(self, combo, k):
"""
input: string[] combo, int k
return: string[]
"""
# write your solution here
mydict={}
for char in combo:
if char in mydict:
mydict[char]+=1
else:
mydict[char]=1
sorted_tuple=sorted(mydict.items(), key= lambda kv: -kv[1] )
return [x[0] for x in sorted_tuple][:k]前面部分是O(n), sort部分都是O(nlogn), 最后一步还是O(n), 最终就是O(nlogn)
这里输出的是dict_keys
如果使用collections这个package，然后把items转成list 可以通过。
class Solution(object):
def topKFrequent(self, combo, k):
"""
input: string[] combo, int k
return: string[]
"""
# write your solution here
import collections
import heapq
counts = collections.Counter(combo)
items = list(counts.items())
items.sort(key=lambda item:(-item[1],item[0]))
return [item[0] for item in items[0:k]]另外还可以用heap做这道题，也就是把整理好的dict一个个push到max heap或者min heap里。因为Python内置函数的heap是一个min heap，如果想用它做max heap，在每个元素push进去的时候对value取负号。然后在有元素可pop并且pop出来的元素数量<=k的前提下一个个pop元素, append到result上，然后反过来输出。
class Solution(object):
def topKFrequent(self, combo, k):
"""
input: string[] combo, int k
return: string[]
"""
# write your solution here
# max heap
mydict={}
for char in combo:
if char in mydict:
mydict[char]+=1
else:
mydict[char]=1
import heapq
freq=[]
for char in mydict.keys():
heapq.heappush(freq, (-mydict[char], char))
topk, i =[],0
while i < k and len(freq)>=1:
topk.append(heapq.heappop(freq)[1])
i+=1
return topkExample: Palindromic Testing
给一个单词，测试它能否被写成回文数的形式。能满足回文的条件，那就必须满足除了中间的数可能一个外，其余的都是偶数个；换句话说，奇数的字母只有1个，其余都是偶数个。所以我们需要建立字母到频率的字典，计算频率的个数。
def is_palindromic(word):
freq = {}
for i in range(len(word)):
if word[i] in freq:
freq[word[i]]+=1
else:
freq[word[i]]=1
odd_cnt = 0
for key in freq.key():
if freq[key]%2==1:
odd_cnt += 1
if odd_cnt > 1:
return False
return True Time Complexity: O(n)
Space Complexity: O(C) C是distinct chars in string
Given an array nums and a target value k, find the total number of subarrays that sums to k.
Nums = [1,6,5,2,3,4,0] k=7, return 4 prefixS = [0,1,7,12,14,17,21,21] prefixS[j]-prefixS[i]==target <--->prefixS[j]-target==prefixS[i]
O(n) time, O(C) space, c is the number of distinct values
class Solution(object):
def numOfSubarraySumToK(self, nums, k):
"""
input: int[] nums, int k
return: int
"""
# write your solution here
sums, count = 0,0
mydict={}
for num in nums:
if sums not in mydict:
mydict[sums]=0
mydict[sums]+=1 #注意这句和下句的先后顺序
sums+=num
if sums-k in mydict:
count+=mydict[sums-k]
return countExample: Nearest repeated entries in an array
重复的单词最近的距离 key是单词，value是位置，距离只需要减一下、更新为距离。
def nearest_repeat (arr):
word_ind = {}
dist = float('inf')
for i in range(len(arr)):
if arr[i] in word_ind:
dist = min(dist, i -word_ind[arr[i]])
word_ind[arr[i]] = i
return distTime Complexity: O(n)
Space Complexity: O(C) C是distinct entries in arr
return index, O(n) time and O(n) space
def 2sum(nums, target):
if len(nums)<=1:
return False
dict={}
for i in range (nums):
if nums[i] in dict:
return (dict[num[i]], i)
else:
dict[target-nums[i]]=i
return FalseExample: Nearest repeated entries in an array
Example: Longest Contained Range
brute-force: sort, O(nlogn), search, O(n)
set: “中心开花，左右出发“，以任何一个元素出发，往两边扩展
先放进集合里
pop 任取元素，左右扩展
def longest_contained_range(arr):
unprocessed = set(arr)
maxlen = 0
while unprocessed:
elem = unprocessed.pop()
lower = elem - 1
while lower in unprocesssed:
unprocessed.remove(lower)
lower = lower-1
upper = elem + 1
while upper in unprocessed:
unprocessed.remove(upper)
upper = upper+1
maxlen = max(maxlen, upper-lower-1)
return maxlen时间 O(n)
空间 O(C)
list vs. dictionary
list存储的是单独的元素，而字典存储的是对应关系（mapping），或者叫它映射。我们叫它Key-value pair，键值-存储值。
对任何一个数据结构，都需要知道 创建、增、删、查、改
创建
my_dict = {}
grades = {'Ana': 'B', 'John': 'A+', 'Denise': 'A', 'Katy': 'A'}查找
字典没有顺序，只能按key查找，所以必须是存在在字典里的元素，不然直接run下行就会出现key error
grades['John']还有一个函数，get 如果找不到，可以给None
print (grades.get ('Bob'))判断key在不在字典里，就可以用lookup的操作，
'John' in grades #return False
'Daniel' in grades #return True 增改
加一个新的entry、改已有的syntax，都可以很简单的
grades['John'] = 'A'
grades['Ana'] = 'B+'删除
del grades['Ana'] #从字典里取这个key，然后删了
grades.pop('Ana') #随机pop出一个Ana（如果有两个Ana）拿到key的集合
python2 用grades.keys() return的是[‘A’, 'A', 'A+', 'B'] （value的list）
python3 的return是 （value的view）
view都不会占额外的空间，就像是range和xrange的区别
当然也可以用list(dict.keys()) ，占空间呗
拿到value的集合
类似👆
requirements for keys
Key必须unique，不能重复；第二次的一样的值会把第一个覆盖掉
Key必须是immutable的类型 所以X={[1]:0}不对，list unhashable
像Y={(1,2):10}就行，str也行
Dictionary Implementation
字典，hash的实现里，不需要去查找每个元素了，而是有一系列的buckets。每次有一个key，先算hashfunction（key），通过这个值，来得到bucket的序号。hashfunc可以接收任何变量，最后它能计算出一个integer，下面的code中，array_size是一个常数，也就是bucket size. 用算好的hash来%array_size, 得到index，意味着最后要把它放到index的桶里去找。
hash = hashfunc(key)
index = hash % array_sizeHash Collision
假设两个key，x和y，本身x!=y, 但是hash(x)==hash(y), 就有了collision，因为它们被映射到了同一个bucket里，所以在第二行一定一样。
此外，因为array_size是一个定值，即使1不一样了，到2还是有可能一样，那还是会collision。
如果有perfect hashing, array_size又是无穷大（这在实际情况中是不存在的），就不会有冲突。
那么 现实中如何解决hash collision？
策略一： open addressing
如果算出来的数值被占了，发生了hash collision，就占用它最近的没有被占用的单元。
策略二：separate chaining
在每一个bucket里，就做成链表，把下一个人直接占在它后面 worst case就是，如果bucket=1(概率极低), 那么就变成了singly linked list，那么查找的时间复杂度又是O(n)了 不过，on average 还是可以O(1)
Time Complexity of different operations on dictionary
|Operation | Avg | Worst |
Search O(1) O(n)
Add O(1) O(n)
Delete O(1) O(n)
Update O(1) O(n)
Set
有时我们并不关心value，只关心key本身，这个时候dict就退化成了set，集合。集合就是只包含了key的hashtable。需要注意的是，集合本身可变mutable，但是里面包含的元素不变。所以增删查改咯～
Add
x = {"a","b","c","d"}
x.add("e") #one element
x.update({"e", "f"}) #multiple elementsremove
如果remove的元素不在，使用x.remove会报keyerror； 但是使用x.discard("a")不会报
如果从中随意删除任何一个(因为set没有顺序，所以真的不知道删了哪个... )，x.pop()； 如果是清空，x.clear() ；
union
下面是集合操作的取并集 这个x和y是用set（）把list变成集合
x = set(["Postcard", "Radio", "Telegram"])
y = set([ "Radio", "Television"])
print x.union(y)
更多
set也有set comprehension
{expression for value in collection if condition}
squared = {x**2 for x in [1,1,2]}Recap
One to one mapping
<key, value> pair, key map to value
Key, no duplicates
Value, allow duplicates
hash_set is a set {1,3}, it only contains keys
In python, hash_set is set; hash_table is dictionary
题目
find one missing from unsorted array
use a set, iterate over the input array Average O(n) Worst O(n^2)
for each number from 1 to n: find if it's in the set Average O(n) Worst O(n^2)
优化 use a boolean[]
因为连续，可以放进物理连续的boolean array里 Step 1: for each element in the input array (value=i), put it into the seen[i]=true O(n) Step 2: for each element from 1...n: check if seen[i]==true O(n)
数学
等差数列求和，减去sum of input array，剩下的就是output Space O(1) but it may overflow
bit operation XOR
交换律 a XOR b = b XOR a
结合律 a XOR (b XOR c) = (a XOR b) XOR c
0是单元 0 XOR a = a
a XOR a =0
class Solution(object):
def missing(self, array):
"""
input: int[] array
return: int
"""
# write your solution here
n = len(array)+1
xor = 0
for i in range(1, n+1):
xor ^= i
for num in array:
xor ^= num
return xorfind common numbers between 2 sorted arrays a[M], b[N]
需要确认 如果有重复元素怎么办
Assume没有重复 或者 有重复元素只输出一次
Hashset
比较大小，把小的放进hashset
Step 1: Insert all elements from smaller array a into the hash set
Step 2: For each element in array b, check if it's in the HashSet or not
Time = O(M+N) average, worst O(M^2+N*M) Space = O(M)
谁小移谁
不相等就谁小移谁，相等就分别往前
Time = O(M+N) Space = O(1)
class Solution(object):
def common(self, A, B):
"""
input: int[] A, int[] B
return: Integer[]
"""
# write your solution here
i, j = 0, 0
result = []
while (i<len(A) and j<len(B)):
if (A[i]==B[j]):
result.append(A[i])
i+=1
j+=1
elif A[i]<B[j]:
i+=1
else:
j+=1
return result如果M<<<N Binary Search
For each element in b[N], run binary search M times.
Time = O(MlogN) Space = O(1)
2 sum sorted
因为是sorted，所以可以用2 pointers的方法，利用增加和减小的单调性：一个往前移一个往后移；如果现在的和比target小，移动i往后；如果比现在的target大，移动j往前。
def two_sum(list, target):
i,j = 0, len(list)-1
while i<j:
if list[i]+list[j] < target:
i += 1
elif list[i]+list[j] > target:
j -= 1
elif list[i]+list[j] == target:
return True
return False
# Time O(n)
# Space O(1)2 sum unsorted
利用set的性质，经过的数字都存下来；用target的数字和当前经过的数字相减，如果得到的结果在之前的set里，就找到了，return true。否则，false。
def two_sum(list, target):
hashset = set()
for key in list:
if (target-key) in hashset:
return True
else:
hashset.add(key)
return False
# Time O(n)
# Space O(n)[10, 2, 2, 13, 2], target 4
如果题目要output多少对，用一个dict，存count： {10:1, 2:2, ...}
如果题目要output哪些index的组合，dict里是list of index: {10:(0), 2:(1,2), ...}
def two_sum_duplicate(arr, sum):
dic = {}
count = 0
for key in arr:
if sum-key in dic:
count+=dic[sum-key]
if key in dic:
dic[key]+=1
else:
dic[key]=1
return count
# Time O(n)
# Space O(n)3 sum unsorted
方法一：走n遍的2 sum。Time O( ) Space O(n)
方法二：先排序，反正已经O( )了，就算先排序也不会影响这个时间复杂度，那就排序吧！可以让空间复杂都变成O(1)。
def three_sum (array, target):
if array is None or len(array)==0:
return False
array.sort()
for i in range(len(array)-2):
start = i + 1
end = len(array)-1
while start<end:
tmp_sum = array[start] + array[end] + array[i]
if tmp_sum == target:
return True
elif tmp_sum < target:
start += 1
else:
end -= 1
return False
# Time O(n2)
# Space O(1)4 sum unsorted
方法一：走n遍的3 sum。O( )
for i in range(len(array)-3):
for j in range(i+1, len(array)-2):
#2sum
# Time O(n3)
# Space O(1)方法二：变成2个2sum，如何找到pair of 2 sum, 和是target。 1. 先配对 O( ) 2. sort一遍或者hashset O( ) 3. 在配对的时候要检查它是否是用过的 O(1)
class twoSumPair:
def __init__(self, index1, index2):
self.index1 = index1
self.index2 = index2
self.number1 = array[index1]
self.number2 = array[index2]
self.sum = self.number1 + self.number2
pairlist=[twoSumPair(0,1), twoSumPair(0,2), twoSumPair(0,3), twoSumPair(0,4),
twoSumPair(1,2),twoSumPair(1,3)...]k sum
在array里选k个数字组成sum=target。DFS，k个数字的subset
2 difference sorted
2 pointers，错一位同向而行。因为如果是相向而行，目前的值大于target，那么移动i或者j都行，所以到底移动哪个？ 两个都尝试时间复杂度就会变高。同向而行，如果当前值大于target，移动i向前；如果当前值小于target，移动j向前。
def two_difference(array,target):
i,j = 0, 1
while j<len(array):
if array[j]-array[i] < target:
j += 1
elif array[j]-array[i] > target:
i += 1
elif:
return True
return False
# Time O(n)
# Space O(1)2 difference unsorted
创建set
loop array，检查set里的元素是否等于array[i]-target或者array[i]+target
def two_sum(list, target):
hashset = set()
for key in list:
if (key-target) in hashset or (target+key) in hashset:
return True
else:
hashset.add(key)
return False
# Time O(n)
# Space O(n)Longest sublist without duplicate values.
1 2 3 1 4 3 longest is 2 3 1 4
def longest_sub_list(list):
hashset=set()
longest=0
slow=fast=0
while fast<len(list):
while list[fast] in hashset:
hashset.remove(list[slow])
slow+=1
hashset.add(list[fast])
longest = max(longest, fast-slow+1)
fast+=1
return longestLast updated