时间复杂度：查找数组的模式

Question

Being apart of a challange for beginners, I would like to know if my algorithm is indeed O(n) as I intended it to be.

The idea is simple, I'm given the task to create an algorithm that finds the mode of an integer array. The only catch was that if two integers in the array had the same multiplicity, the mode would be the lesser integer.

I've seen other algorithms around that do the job in O(n logn), however in the challange description it was mentioned that it could be done in O(n).

First of, I created a hash table that stores each integer that is found in the array with a key that represents it's own multiplicity.

If we have an element with the same multiplicity as the maximum multiplicity we check if the new element is less than mode. If it is, the new element becomes the new mode.

I chose Golang for my implementation.

func mode(input []int) (int, error) {

    // Error handeling.
    if len(input) == 0 {
        return -1, errors.New("can't find the mode of an empty array")
    }

    // Initilize a hashtable with key representing the multiplicities.
    m := make(map[int]int)

    mode := 0

    // The biggest multiplicity.
    max := 0

    for _, elem := range input {
        m[elem]++
        if m[elem] > max {
            max = m[elem]
            mode = elem
        }
        if m[elem] == max && mode > elem {
            mode = elem

        }
    }
    return mode, nil
}

Answer 1

More or less. The map insertions and lookups are somewhere between O(1) and O(log n), where n is the number of elements in the map, not in the input array. So your result will be close to O(n), or more accurately somewhere between O(n) and O(n log m) where m is the number of unique entries in the input.