Мой взгляд на Мигрирующую птицу провалился в одном случае - PullRequest
Новая
       65

Мой взгляд на Мигрирующую птицу провалился в одном случае

0 голосов
/ 03 апреля 2020

Обновление: Я полностью упустил из виду сложность, добавленную методом arr.sort (). Таким образом, в Kotlin для массива Int, он компилируется для использования java.util.DualPivotQuicksort , см. , который в свою очередь имеет сложность O (n ^ 2). смотри это . Помимо этого, это также правильный подход.

Я знаю, что это можно решить, сохранив несколько массивов или используя коллекции (что я и отправил), я хочу знать, что я упустил в следующем подходе 

    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, который имеет 73966 элементов для массива. На моей локальной машине этот массив из 73k + элементов вызывал тайм-аут, но я проверил массив до 20k + случайно сгенерированное значение 1..5 и каждый раз, когда это удавалось. Но мне не удалось пройти Тестовый пример 2 с таким подходом. Поэтому, даже несмотря на то, что я в конечном итоге отправил ответ с подходом сбора потоков, мне бы очень хотелось узнать, чего мне не хватает в приведенной выше логи c.

Я запускаю массив l oop только один раз, когда Сложность должна быть O (n), поэтому это не может быть причиной сбоя. Я предварительно сортирую массив в порядке возрастания, и я проверяю >, а не >=, поэтому, если два типа в конечном итоге имеют одинаковое количество, он все равно будет возвращать меньшее из двух типов. И этот подход работает правильно даже для массива 20k + элементов (я получаю тайм-аут для всего, что выше 25k элементов).

1 Ответ

0 голосов
/ 03 апреля 2020

Причина сбоя в том, что эта строка 

 arr.sort()

Сортировка массива занимает O (n logn) времени. Однако, используя что-то вроде карты ha sh, это можно решить за 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
...