arrays - 时间复杂度 : Findning the mode of an array

Question

作为初学者的挑战之一，我想知道我的算法是否确实是我预期的 O(n)。

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

我已经看到其他算法在 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 是 map 中的元素数，而不是输入数组中的元素数。因此您的结果将接近 O(n)，或者更准确地说介于 O(n) 和 O(n log m) 之间，其中 m 是输入中唯一条目的数量。