Разбор задач

В этом уроке разберём несколько решений типичной алгоритмической задачи, для решения которой не требуется знание специфических алгоритмов и структур данных. Рассмотрим преимущества и недостатки разных методов решения, и оценим их сложность по времени и по памяти.

Условие задачи: дан массив nums, состоящий из целых чисел, и целое число val. Нужно удалить все вхождения val в nums и вернуть длину массива после удаления. При подсчёте длины можно не учитывать крайние левые или крайние правые элементы, равные val.

Решение №1

Заведём пустой массив result. Будем проходить по элементам массива nums, и, если элемент не равен val, добавлять его в массив result.

Скопировать кодJSX
def removeTarget(nums, val):
    result = []
    for num in nums:
        if num != val:
            result.append(num)
    return len(result)

Будет выполнено

n

операций сравнения, и в худшем случае

n

операций добавления элемента в массив. Сложность

O(n)

, где

n

— количество элементов в массиве nums.

Решение № 2

Рассмотрим решение без использования дополнительной памяти.

Будем проходить по массиву nums и удалять элемент, если он равен val.

Скопировать кодJSX
def removeTarget(nums, val):
    for i in range(len(nums)):
        i = 0
        while i < len(nums):
            if nums[i] == val:
                del nums[i]
                continue
            else:
                i += 1
    return len(nums)

В худшем случае удалим все элементы массива nums. При удалении элемента нужно подвинуть все справа стоящие от него элементы на один влево.

При первом удалении подвинем

n-1

элемент, при втором —

n-2

элемента, и так далее. На предпоследнем шаге потребуется одно перемещение, а на последнем — ни одного.

Таким образом, всего нужно выполнить перемещений:

(n - 1) + (n - 2) + ... + 1

Это арифметическая прогрессия. Её сумму можно посчитать по формуле:

S_N = \displaystyle \frac{a_1 + a_N}{2} \cdot N

a_1 = 1, a_N = n - 1, N = n

\displaystyle S_N = \frac{n^2}{2}

Получили сложность

O(n^2)

Решение менее эффективное по времени, чем первое.

В одном из следующих уроков мы подробнее разберём сложность операции удаления из массива. Ничего страшного, если пока не до конца понятно, почему сложность алгоритма именно такая.

Решение № 3

Заведём следующие переменные:

start, изначально равную 0;
end, на 1 меньшую длины массива nums;
mid, изначально равную 0.

Пока mid не превосходит end будем выполнять такие действия:

Если элемент на позиции

i

не равен val, поменяем местами элементы на позициях mid и start; Увеличим start и mid на 1.

Иначе увеличим mid на 1.

Вернём из функции значение start.

Скопировать кодJSX
def removeTarget(nums, val):
    start = 0
    end = len(nums) - 1
    mid = 0
    while mid <= end:
        if nums[mid] != val:
            nums[start], nums[mid] = nums[mid], nums[start]
            start += 1
            mid += 1
        else:
            mid += 1
    return start

Цикл продолжается, пока mid не превосходит

n

. Значение mid увеличивается на каждом шаге. То есть в худшем случае нужно выполнить

O(n)

операций. Дополнительная память для работы алгоритма не требуется.