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

Question

作为初学者的挑战之外，我想知道我的算法是否确实像我想要的那样O(n)。

这个想法很简单，我的任务是创建一个找到整数数组模式的算法。唯一的问题是，如果数组中的两个整数具有相同的多重性，则模式将是较小的整数。

我已经看到周围的其他算法在O(n logn)中完成这项工作，但是在挑战描述中提到它可以在O(n)中完成。

首先，我创建了一个哈希表，该表存储数组中找到的每个整数，并带有一个表示其自身多重性的键。

如果我们有一个与最大多重性相同的多重性的元素，我们会检查新元素是否小于模式。如果是，则新元素将成为新模式。

我选择了Golang来实现。

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

或多或少。映射插入和查找介于 O(1( 和 O(log n( 之间，其中 n 是映射中的元素数，而不是输入数组中的元素数。因此，您的结果将接近 O(n(，或者更准确地说，介于 O(n( 和 O(n log m( 之间，其中 m 是输入中唯一条目的数量。