Намерете дума с максимален брой случаи - алгоритъм, намерете

Кой е най-оптималният начин (алгоритъм) за търсене на дума, която има максимален брой случаи в документ?

Отговори:

Намирането на думата, която се случва най-често в даден документ, може да бъде направено в O (n) с просто хистограма [хеширане]:

histogram <- new map<String,int>
for each word in document:
if word in histogram:
histogram[word] <- histogram[word] + 1
else:
histogram[word] <- 1
max <- 0
maxWord<- ""
for each word in histogram:
if histogram[word] > max:
max <- histogram[word]
maxWord <- word
return maxWord

Това е O (n) решение, и тъй като проблемът е ясно Omega (n) проблем, той е оптимален по отношение на голяма О нотация.

1. Сканирайте документа веднъж, като държите сметка колко пъти сте видели всяка уникална дума (може би с помощта на hashtable или дърво, за да направите това).
2. Докато изпълнявате стъпка 1, проследявайте думата, която има най-голям брой от всички думи, които се виждат досега.