Skip to content

Instantly share code, notes, and snippets.

@MinweiShen
Created March 24, 2015 01:15
Show Gist options
  • Save MinweiShen/56b9c8b9fd5dc0d28a86 to your computer and use it in GitHub Desktop.
Save MinweiShen/56b9c8b9fd5dc0d28a86 to your computer and use it in GitHub Desktop.
Misra_Gries algorithm
def Misra_Gries(file,k):
result = {}
to_delete = []
with open(file,"r") as f:
for l in f.readlines():
chars = l.split()
for ch in chars:
to_delete = []
if ch in result:
result[ch] = result[ch] + 1
else:
if len(result) < k-1:
result[ch] = 1
else:
for c in result:
if result[c] == 1:
to_delete.append(c)
else:
result[c] = result[c] - 1
for c in to_delete:
del result[c]
return result
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment