O（n）具有O（1 / epsilon）空间的重击者？(O(n) Heavy-Hitters with O(1/epsilon) space?)

 我知道重击手的以下算法： 
 
Algorithm findHeavyHitters(epsilon, inputStream)
    integer k = ceiling(1 / epsilon) - 1
    initialize hashmap H of size k

    while an item i from the input stream arrives:
        if H[i] exists
            increment the value associated with H[i]
        elsif number of items in H < k
            put H[i] into map with value of 1
        elseif there exists an entry j with a value of 0
            remove j and put H[i] into map with value of 1
        else
            decrement all values in H by 1
    endwhile

    return H
 
 如果我错了，请纠正我，但这个算法不能在O（n）中运行。 是否可以修改此算法，使其在O（n）中运行，同时保持O（1 / epsilon）空间的使用？ 
 
 对于数据流，算法的要点是返回顶部epsilon * t项。 Epsilon以百分比形式给出（例如，输入0.1表示至少发生10％的数据）。 

I know of the following algorithm for heavy-hitters:
 
Algorithm findHeavyHitters(epsilon, inputStream)
    integer k = ceiling(1 / epsilon) - 1
    initialize hashmap H of size k

    while an item i from the input stream arrives:
        if H[i] exists
            increment the value associated with H[i]
        elsif number of items in H < k
            put H[i] into map with value of 1
        elseif there exists an entry j with a value of 0
            remove j and put H[i] into map with value of 1
        else
            decrement all values in H by 1
    endwhile

    return H
 
Correct me if I'm wrong, but this algorithm does not run in O(n). Is it possible to modify this algorithm so that it runs in O(n) while maintaining the O(1/epsilon) use of space?
 
For a stream of data, the point of the algorithm is to return the top epsilon*t items. Epsilon is given as a percentage (e.g. input 0.1 for data that occurs at least 10% of the time).

原文：https://stackoverflow.com/questions/37851407