改进计数时间功能

Question

我是Kotlin(和Java(的新手。为了学习语言，我正试图从一个网站上解决一些问题。

这个问题很简单，直接来说，函数必须计算IntArray中包含最大值的次数。我的函数也适用于较小的数组，但似乎超过了较大数组允许的时间限制(错误：您的代码没有在时间限制内执行(。

fun problem(inputArray: Array<Int>): Int {
// Write your code here
val n: Int = inputArray.count{it == inputArray.max()}
return n
}

因此，当我试图改进时，我并不是在寻找一个更快的解决方案，而是在寻找一些关于我可以自己寻找更快解决方案的主题的提示。

非常感谢！

Answer 1

在无序数组中，您可以触摸每个元素来计算inputArray.max()。所以inputArray.count()遍历所有元素，并调用遍历所有元素的max()。

因此，n个元素的运行时间增加了n^2。

将inputArray.max()存储在一个额外的变量中，就有了一个线性运行时。

val max = inputArray.max()
val n: Int = inputArray.count{ it == max }