максимальное количество последовательных в swift

Question

Я пытаюсь выучить Swift, решая простые вопросы об интервью на LeetCode.

Вопрос состоит в следующем:

Для заданного двоичного массива найдите максимальное количество последовательных 1 в этом массиве.

Пример 1:

Ввод: [1,1,0,1,1,1]

Вывод: 3

Объяснение: Первые две цифры или последние три цифры являются последовательными 1 с.Максимальное количество последовательных 1 с составляет 3.

Примечание:

Входной массив будет содержать только 0 и 1. Длина входного массива является положительным целым числом и будетне превышает 10 000

Я решил следующий вопрос, без проблем, он запускает и покрывает тестовые случаи, но он показывает, что мое представление только на 73 процента быстрее, чем все представления.Интересно, есть ли лучший способ решить этот вопрос?Моя сложность времени решения O (n).

class Solution {
    func findMaxConsecutiveOnes(_ nums: [Int]) -> Int {

        var globalMax = 0
        var localMax = 0

        for num in nums
        {
           if num == 1
           {
              localMax += 1
              globalMax = max(globalMax, localMax)
           }
           else
           {
                localMax = 0
           }  
        }
        return globalMax
    }
}

Answer 1

Две незначительные корректировки, проверка размера массива на самом деле не нужна, и вызов max требуется только тогда, когда найден 0 и в конце

func findMaxConsecutiveOnes(_ nums: [Int]) -> Int {
    var globalMax = 0
    var localMax = 0

    for num in nums {
       if num == 1 {
          localMax += 1              
       } else {
            globalMax = max(globalMax, localMax)
            localMax = 0
       }  
    }
    return max(globalMax, localMax)
}

Я провел эксперимент с разбиением и уменьшением иэта комбинация выглядит немного быстрее, чем приведенная выше, но примерно такая же, как в комментариях

func findMaxConsecutiveOnes3(_ nums: [Int]) -> Int {
    return nums.split(separator: 0).reduce(ArraySlice<Int>(), { ($1.count > $0.count) ?  $1 : $0 }).count
}

Answer 2

Ваш вопрос больше подходит для сайта Code Review .Рейтинги в LeetCode не надежны и могут варьироваться от подачи к следующему (с тем же кодом).

Вот решение, которое позволяет избежать if .. else (исходный код Java здесь ):

func findMaxConsecutiveOnes4(_ nums: [Int]) -> Int {
    var globalMax = 0
    var localMax = 0

    for num in nums {
        localMax *= num
        localMax += num
        globalMax = max(globalMax, localMax)
    }
    return globalMax
}

Для бенчмаркинга я использовал следующий код:

let array = (0...10_000).map { _ in Int.random(in: 0..<2) }

let start1 = mach_absolute_time()
let x1 = findMaxConsecutiveOnes1(array)
let end1 = mach_absolute_time()
print("1st", x1, Double(end1 - start1)/Double(1e3), "us")

let start2 = mach_absolute_time()
let x2 = findMaxConsecutiveOnes2(array)
let end2 = mach_absolute_time()
print("2nd", x2, Double(end2 - start2)/Double(1e3), "us")

let start3 = mach_absolute_time()
let x3 = findMaxConsecutiveOnes3(array)
let end3 = mach_absolute_time()
print("3rd", x3, Double(end3 - start3)/Double(1e3), "us")

Где findMaxConsecutiveOnes - ваше решение, findMaxConsecutiveOnes2 - Иоакима , а findMaxConsecutiveOnes3 - предложенное в этом ответе.

Скомпилировано с оптимизацией (-O) в терминале, вот время выполнения:

• findMaxConsecutiveOnes1: 49.079 us
• findMaxConsecutiveOnes2: 54.016 us
• findMaxConsecutiveOnes3: 14.883 us

---

Быстрее, чем 100,00% онлайн-заявок Swift (на данный момент)

Следующая реализация рассматривается какна данный момент самый быстрый по LeetCode:

func findMaxConsecutiveOnes(_ nums: [Int]) -> Int {

    guard !nums.isEmpty else {
        return 0
    }

    var globalMax = 0
    var localMax = -1

    for i in 0..<nums.count {
        if nums[i] != 1 { //It is faster than: if nums[i] == 0
            localMax = i
        }
        globalMax = max(globalMax, i - localMax)
    }
    return globalMax
}

Здесь - это оригинальная реализация C ++.

В моих тестах он не работал должным образом: 33.615 us в массиве из 10 000 элементов.

Но в массивах меньшего размера оказалось самым быстрымolution .

---

Еще более быстрое решение

Это самое быстрое:

func findMaxConsecutiveOnes(_ nums: [Int]) -> Int {

    guard !nums.isEmpty else {
        return 0
    }

    var globalMax = 0
    var lastZeroIdx = -1

    for i in 0..<nums.count {
        if nums[i] == 0 {
            globalMax = max(lastZeroIdx == -1 ? i : i - lastZeroIdx - 1, globalMax)
            lastZeroIdx = i
        }
    }
    globalMax = max(lastZeroIdx == -1 ? nums.count : nums.count - lastZeroIdx - 1, globalMax)
    return globalMax
}

Он был перенесен из этой реализации java.

В моих тестах я не мог заметить каких-либо улучшений во времени выполнения ни на малых (10 элементов), ни на больших (10 000 элементов)-> 42.363 us) массивов.

Answer 3

Возможно, они ожидают некоторых специфичных для Swift трюков.

Если нет - я мог бы предположить, что система проверки не любит вычисления для каждого 1 элемента.

Вы можете вычислить глобальный максимум только в случае1-0 переход (или в конце массива).В этом случае вам также нужно запомнить индекс 1 в случае изменения 0-1.