Kotlin中数组最大整数计数：求更优简洁且优于O(nlogn)的写法

当然有！你的O(n)思路完全正确——这比排序法的O(nlogn)高效多了，我们可以借助Kotlin的标准库函数，把代码写得更简洁、更符合Kotlin惯用风格，同时保持最优的时间复杂度。

优化方案1：用标准库函数简化（两次遍历，O(n)） #

原代码的核心逻辑是找最大值+计数，我们可以用maxOrNull()（比max()更安全，避免空数组抛出异常）配合count()函数直接实现：

fun countMax(ar: Array<Int>): Int {
    val maxValue = ar.maxOrNull() ?: return 0 // 空数组直接返回0
    return ar.count { it == maxValue }
}

甚至可以压缩成一行函数：

fun countMax(ar: Array<Int>) = ar.maxOrNull()?.let { max -> ar.count { it == max } } ?: 0

优化方案2：一次遍历完成（O(n)，常数更小） #

如果想减少一次数组遍历（时间复杂度还是O(n)，但常数开销更低），可以用fold函数同时跟踪当前最大值和计数：

fun countMax(ar: Array<Int>): Int {
    return ar.fold(Pair(Int.MIN_VALUE, 0)) { (currentMax, count), num ->
        when {
            num > currentMax -> num to 1
            num == currentMax -> currentMax to count + 1
            else -> currentMax to count
        }
    }.second
}

简化主函数 #

你的主函数里的n其实是多余的（数组本身的长度就是ar.size），可以简化成：

fun main() {
    val scanner = Scanner(System.`in`)
    scanner.nextLine() // 跳过第一行的n，因为不需要它
    val ar = scanner.nextLine().split(" ").map { it.trim().toInt() }.toTypedArray()
    println(countMax(ar))
}

或者用Kotlin更简洁的IO写法：

fun main() {
    val ar = readLines()[1].split(" ").map { it.toInt() }.toTypedArray()
    println(ar.maxOrNull()?.let { max -> ar.count { it == max } } ?: 0)
}

为什么这些写法更好？ #

• 保持了O(n)的时间复杂度：无论是两次遍历还是一次遍历，都远优于排序法的O(nlogn)，尤其适合处理大型数组。
• 更符合Kotlin的函数式风格：用标准库函数替代手动循环，代码可读性更高，也更简洁。
• 更健壮：maxOrNull()处理了空数组的边界情况，避免原代码中可能出现的空指针异常。

内容的提问来源于stack exchange，提问作者UmAnusorn