Задать вопрос

В чем я ошибся в решении задачи VK EDUCATION?

Задание:
На вход подается не отсортированный массив и некоторое число element. Необходимо написать функцию, которая вернет количество элементов, которые не равны числу element. При этом входной массив после работы функции не должен содержать в себе значения равные element.

Формат входных данных
9
7 8 1 3 11 3 9 4 3
3

Формат выходных данных
5

Мое решение, которое не принимается «Wrong Answer» — неверный ответ:
def func(num, arr, el):
    for i in arr[::-1]:
        if i == el:
            arr.remove(el)

    return len(arr)
  • Вопрос задан
  • 1275 просмотров
Подписаться 2 Простой 18 комментариев
Решения вопроса 1
@codingoleg
Ваше решение технически верное, но имеет 2 недостатка, особенно для больших массивов и/или частых операций.
Во-первых, вы создаёте копию массива для итерации (arr[::-1]), который занимает памяти столько же, сколько оригинальный массив. Во-вторых, вы удаляете элементы из массива по значению (remove), а не по индексу (del), что существенно замедляет выполнение. Рекомендую ознакомиться, как массив устроен под капотом и временную сложность добавления, вставки, изменения и удаления в него. Отсюда также будет понятно, почему одновременная итерация в прямом порядке с помощью цикла for и удаление элементов из массива - это плохая идея. Вот вам 4 функции с бенчмарками, из которых первая ваша:
import random
import time


def func(arr, el):
    for i in arr[::-1]:
        if i == el:
            arr.remove(el)
    return len(arr)


def remove_reverse(arr, el):
    for i in reversed(arr):
        if i == el:
            arr.remove(el)
    return len(arr)


def del_by_index_reverse(arr, el):
    for i in reversed(range(len(arr))):
        if arr[i] == el:
            del arr[i]
    return len(arr)


def del_by_index_while(arr, el):
    i = 0
    while i < len(arr):
        if arr[i] == el:
            # Удаляем значение по индексу и не сдвигаем указатель i
            del arr[i]
        else:
            i += 1
    return len(arr)


# Создаем массив из 100000 случайных цифр от 0 до 9 и сделаем по копии для каждой функции
arr1 = [random.randint(0, 9) for num in range(100_000)]
arr2 = arr1[:]
arr3 = arr1[:]
arr4 = arr1[:]
el = 5

start = time.perf_counter()
print(func(arr1, el))
print(time.perf_counter() - start)

start = time.perf_counter()
print(remove_reverse(arr2, el))
print(time.perf_counter() - start)

start = time.perf_counter()
print(del_by_index_reverse(arr3, el))
print(time.perf_counter() - start)

start = time.perf_counter()
print(del_by_index_while(arr4, el))
print(time.perf_counter() - start)
Ответ написан
Комментировать
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы