我对候鸟的看法失败了一个案例

Question

更新： 我完全忽略了 arr.sort() 方法增加的复杂性。所以在 Kotlin 中，对于 Int 数组，它编译为使用 java.util.DualPivotQuicksort which in turn has complexity of O(n^2). see this。除此之外，这也是一种有效的方法。

我知道可以通过保留多个数组或使用集合（这是我最终提交的）来解决，我想知道我在以下方法中遗漏了什么

    fun migratoryBirds(arr: Array<Int>): Int {
        var maxCount = 0
        var maxType = 0
        var count = 0
        var type = 0

        arr.sort()
        println(arr.joinToString(" "))
        for (value in arr){

            if (type != value){
                if (count > maxCount){
                    maxCount = count
                    maxType = type
                }
                // new count values
                type = value
                count = 1
            } else {
                count++ 
            }
        }
        return maxType
    }

此代码通过了除测试用例 2 之外的所有场景，测试用例 2 具有 73966 个数组项。在我的本地机器上，那个 73k+ 元素的数组导致超时，但我确实测试了最多 20k+ 个随机生成的值 1..5 的数组，并且每次都成功。但是我无法通过这种方法通过测试用例 2。因此，即使我最终使用收集流方法提交了答案，我真的很想知道在上述逻辑中我可能遗漏了什么。

我是运行数组循环只一次复杂度应该是O(n)，所以这不能成为失败的原因。我按升序对数组进行预排序，我正在检查 > 而不是 >=，因此，如果两种类型最终具有相同的计数，它仍然会 return两种。而且这种方法即使对于 20k+ 元素的数组也能正常工作（对于超过 25k 元素的任何内容我都会超时）。

Answer 1

它失败的原因是这一行

 arr.sort()

对数组进行排序需要 O(n logn) 时间。但是，使用哈希映射之类的东西可以在 O(n) 时间内解决。

这是我为您提供的一个快速 python 解决方案

# Complete the migratoryBirds function below.
def migratoryBirds(arr):
    ans = -1
    count = -1
    dic = {}
    for x in arr:
        if x in dic:
            dic[x] += 1
        else:
            dic[x] = 1
        if dic[x] > count or dic[x] == count and x < ans:
            ans = x
            count = dic[x]
    return ans

我对候鸟的看法失败了一个案例

My take on Migratory Bird is failing one case

logic

concept

kotlin