Выполнение перемещения нулей к концу упражнения по программированию массива

Question

Интересно, почему мое решение этой проблемы LeetCode "Move Zeros" медленнее, чем большинство других представлений.Есть ли лучший способ подойти к этой проблеме, чтобы сделать ее быстрее?

Вопрос заключается в следующем:

Учитывая массив nums, напишите функцию, чтобы переместить все 0 вконец его при сохранении относительного порядка ненулевых элементов.Вы должны сделать это на месте, не делая копию массива.

Пример:

Вход: [0,1,0,3,12]

Выход: [1,3,12,0,0]

Это мое решение:

 func moveZeroes(_ nums: inout [Int]) {
    var index = 0
    for (i,n) in nums.enumerated()
    {
        if n != 0
        {
            nums[index] = n
            index += 1
        }

    }

    while index < nums.count
    {
        nums[index] = 0
        index += 1
    }
}

LeetCode предоставляет мне такую ​​статистику:

Время выполнения: 52 мс, быстрее, чем 40.50% изОнлайн-подача Swift для Move Zeroes.
Использование памяти: 19,4 МБ, менее 13,33% онлайн-заявок Swift для Move Zeroes.

РЕДАКТИРОВАНИЕ 1:

Если я подхожу к проблеме следующим образом, она не перемещает нули в конце:

РЕДАКТИРОВАТЬ 2:

Answer 1

Одним из быстрых решений является смещение ненулевых элементов влево на количество нулей, встречающихся до тех пор:

func moveZeroes(_ nums: inout [Int]) {
    var offset = 0
    for i in 0..<nums.count {
        if nums[i] == 0 { offset += 1 }
        else { nums.swapAt(i, i-offset) }
    }
}

Это решение занимает ровно N шагов, и на каждом шаге мы либо выполняем сложениеили своп, который достаточно быстрый.

Ваше решение, с другой стороны, потребовало двух итераций, что привело к 2 * N шагам, поэтому оно было медленнее других решений.

Answer 2

Вот 36-миллиметровое решение для вас:

class Solution {
    func moveZeroes(_ nums: inout [Int]) {

        if nums.count < 2 {
            return
        }

        var j = 0

        while j < nums.count, nums[j] != 0 {
            j += 1
        }

        if j < nums.count - 1 {
            for i in j+1..<nums.count {
                if nums[i] != 0 {
                    nums.swapAt(i, j)
                    j += 1
                }
            }
        }
    }
}

Answer 3

Другой подход - алгоритм полуустойчивого разбиения.Преимущество состоит в том, что элементы меняются местами, а не удаляются и вставляются / добавляются.

Полустабильный означает, что порядок левой стороны точки разделения сохраняется.

extension Array {

    mutating func halfStablePartition(indexes : IndexSet) { // code is O(n)
        guard var i = indexes.first, i < count else { return }
        var j = index(after: i)
        var k = indexes.integerGreaterThan(i) ?? endIndex
        while j != endIndex {
            if k != j { swapAt(i, j); formIndex(after: &i) }
            else { k = indexes.integerGreaterThan(k) ?? endIndex }
            formIndex(after: &j)
        }
    }
}

var input = [0,1,0,3,12]

let indices = IndexSet(input.indices.filter{input[$0] == 0})
input.halfStablePartition(indexes: indices)

Answer 4

Swift 4.2 или более поздней версии с использованием removeAll метода мутирования:

Прекращение ввода:

class Solution {
    func moveZeroes(_ nums: inout [Int]) {
        var counter = 0
        nums.removeAll {
            if $0 == 0 {
                counter += 1
                return true
            }
            return false
        }
        nums += repeatElement(0, count: counter)
    }
}

---

Аналогичный подход для Swift 4.1 или более ранней версии

func moveZeroes(_ nums: inout [Int]) {
    var counter = 0
    nums.indices.reversed().forEach {
        if nums[$0] == 0 {
            counter += 1
            nums.remove(at: $0)
        }
    }
    nums += repeatElement(0, count: counter)
}

---

var input = [0,1,0,3,12]
moveZeroes(&input)
input   // [1, 3, 12, 0, 0]

---

Подход без мутаций:

func moveZeroes(_ nums: [Int]) -> [Int] {
    var counter = 0
    return nums.filter {
        if $0 == 0 { counter += 1 }
        return $0 != 0
    } + repeatElement(0, count: counter)
}

---

let  input = [0,1,0,3,12]

let zerosMoved = moveZeroes(input)
zerosMoved   // [1, 3, 12, 0, 0]

Answer 5

Я бы лично использовал:

input = input.filter { $0 != 0 } + input.filter { $0 == 0 }

, который можно упростить до одного прохода:

let nonZeros = input.filter { $0 != 0 }
input = nonZeros + Array(repeating: 0, count: input.count - nonZeros.count)

РЕДАКТИРОВАТЬ: простейшей версией без создания нового массива будет некоторая примитивная версия пузырьковой сортировки, например:

var numZeros = 0

// iterate array from start to end
for (offset, element) in input.enumerated() {
    if element == 0 {
        // count every zero
        numZeros += 1
    } else if numZeros > 0 {
        // move every non-zero element left
        input[offset - numZeros] = element    
        // replace with zero
        input[offset] = 0
    }
}

Answer 6

Из того, что я вижу, вероятно, другие заявки делают это

• Проверьте и посчитайте 0 в строке
• Удалите 0 в
• Замените число 0 вконец строки

Вне всякого сомнения, логичный метод, но я бы сказал, что вы просто выбираете основные задачи и выполняете их.