HastTable and Dictionary

Posted on Edited on In ,

Overview

There are several similar data structure.

  • HashTable / Dictionary
    • Key/value
    • dic = {} in Python
    • dic[key] = value
  • HashSet
    • No repeated values
    • se = set() in Python
    • se.add(item) se.remove(item)

The time complexity of search in HashTable’s key or HashSet is O(1)

Useful functions

  • collections.Counter(list) can count the element in the list and generate a dictionary
  • for key, value in dic.items() can iterate the key and value at the same time
  • sorted(dic.keys()) is sorting the keys
  • dic.get(key, value) return the dic[key] if the key in dic, otherwise return value you give

Samples

No.1 Two Sum

1
2
3
4
5
6
dic = {} 
for i, item in enumerate(nums):
    if target - item in dic:
        return [i, dic[target-item]]
    else:
        dic[item] = i

No.138 Copy List with Random Pointer

No.202 Happy Number

No.136 Single Number

1
2
3
4
5
6
7
se = set()
for num in nums:
    if num in se:
        se.remove(num)
    else:
        se.add(num)
return se.pop()

No.217 Contains Duplicate

Used for record the index

No.3 Longest Substring Without Repearting Characters

Used for record the count

No.49 Group Anagrams

1
2
3
4
5
6
7
8
9
10
11
12
dic = {}
for str_ in strs:
    form = dict(collections.Counter(str_))
    form_t = [0 for _ in range(26)]
    for (key, value) in form.items():
        form_t[ord(key) - 97] = value
    form_t = str(form_t)
    if form_t in dic:
        dic[form_t].append(str_)
    else:
        dic[form_t] = [str_]
return dic.values()

No.347 Top K Frequent Elements
Swap the key and values 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
form = dict(collections.Counter(nums))
form_r = {}
for key, value in form.items():
    if value in form_r:
        form_r[value].append(key)
    else:
        form_r[value] = [key]

sort_fre = sorted(form_r)[::-1]
ans = []
count = 0
index = 0
while count < k:
    ans.extend(form_r[sort_fre[index]])
    count += len(form_r[sort_fre[index]])
    index += 1
    
return ans

No.387 First Unique Character in a String

No.242 Valid Anagram

No.350 Intersection of Two Arrays II

No.36 Valid Sudoku

No.454 4Sum II