Hash Table

Algorithms
TODO, hash table
Catalogue
  1. 1. Implement a Hash Table
  2. 2. 347. Top K Frequent Elements
  3. 3. 268. Missing Number
  4. 4. 349. Intersection of Two Arrays
    1. 4.1. Follow up : two sorted array
  5. 5. Find common elements in 3 sorted Arrays
  • Counter
    1. 1. 299. Bulls and Cows

    • A hash table (hash map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

    • Hash Fucntion
    • Hash Collision
    1. Separate chaining
    2. Open addressing

    Implement a Hash Table

    TODO

    347. Top K Frequent Elements

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    class Solution(object):
        def topKFrequent(self, nums, k):
            cnt = collections.defaultdict(int)
            for n in nums:
                cnt[n] += 1

            heap = []
            for key in cnt.keys():
                heapq.heappush(heap, (cnt[key], key))
                if len(heap) == k+1:
                    heapq.heappop(heap)
            return [key for c, key in heap]

    268. Missing Number

    1
    2
    3
    4
    5
    6
    7
    class Solution(object):
        def missingNumber(self, nums):
            nset = set(nums)
            n = len(nums)
            for i in xrange(n+1):
                if i not in nset:
                    return i

    349. Intersection of Two Arrays

    Time : O(m + n), Space : O(m + n)

    1
    2
    3
    class Solution(object):
        def intersection(self, nums1, nums2):
            return list(set(nums1)&set(nums2))

    Follow up : two sorted array

    • Binary Search, Time : O(mlogn), Space : O(1)
    • Two pointers, Time : O(m + n), Space : O(1)

    Find common elements in 3 sorted Arrays

    1. Solution1: three Pointers
      How to move each pointer

    2. Solution2: find common elements a1,a2 then a3

    Counter

    299. Bulls and Cows

    We usually use hash table to do things like counter!

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution(object):
        def getHint(self, secret, guess):
            bulls = 0
            for ch1, ch2 in zip(secret, guess):
                if ch1 == ch2:
                    bulls += 1

            cnt = [0] * 10
            for ch in secret:
                cnt[ord(ch)-ord('0')] += 1
            common = 0
            for ch in guess:
                if cnt[ord(ch)-ord('0')] != 0:
                    common += 1
                    cnt[ord(ch)-ord('0')] -= 1
            cows = common - bulls
            return str(bulls) + "A" + str(cows) + "B"

    Share