作为初学者的挑战之一,我想知道我的算法是否确实是我预期的 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
}
最佳答案
或多或少。映射插入和查找介于 O(1) 和 O(log n) 之间,其中 n 是 map 中的元素数,而不是输入数组中的元素数。因此您的结果将接近 O(n),或者更准确地说介于 O(n) 和 O(n log m) 之间,其中 m 是输入中唯一条目的数量。
关于arrays - 时间复杂度 : Findning the mode of an array,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49695937/