Алгоритмическое решение задачи на удаление повторяющихся элементов в одномерном массиве

Question

Всем здравствуйте! Вот формулировка задачи (предполагается, что её нужно решить на Python): В одномерном массиве удалить (алгоритмически) повторные вхождения элементов. Нельзя использовать del, remove, pop. Срезы можно использовать только 1 раз. Я решила эту задачу, но не алгоритмическим способом:

n = int(input('Enter the size: '))
array = []
for i in range(n):
    array.append(int(input('Enter an element: ')))
length = len(array)
array.append(array[0])
for i in range(1,length):
    if array[i] not in array[:i]:
        array.append(array[i])
array = array[length:]
print(array)

Не могли бы вы натолкнуть меня на мысль, какой алгоритм предполагается использовать для решения данной задачи? P.S: Ещё у меня есть небольшая просьба: основываясь на формулировке задачи, могли бы вы подсказать, где можно порешать подобные? Пробовала искать на LeetCode, GeeksforGeeks, Codeforces, Codewars и т.д., однако там подобного не нашла. Возможно, это именно эта задача была придумана преподавателями кафедры в университете, в котором я обучаюсь. К сожалению, нам не дают решать дополнительные задания. Мне не хватает практики, поэтому обращаюсь сюда. Подскажите, пожалуйста, какие ресурсы использовать, чтобы отточить навык решения задач. Буду благодарна)

Answer 1

Думаю, такое решение понравится преподвателю. Сперва упорядочиваем массив (честно говоря сортировка в Питоне может потребовать линейной дополнительной памяти, притворюсь что никто этого не знает). Затем запускаем классический алгоритм удаления дупликатов: по массиву бегут два указателя - i и j. i бежит без остановок, j задерживается на единицу на каждой паре равных элементов. Элементы копируются из i в j. Когда цикл закончился, обрезаем хвост, присваивая пустой список.

n = int(input('Enter the size: '))
array = [int(input('Enter an element: ')) for _ in range(n)]
array.sort()
i = j = 1
for i in range(1, len(array)):
    if array[i] != array[i - 1]:
        array[j] = array[i]
        j += 1
array[j:] = []
print(array)

P.S. Очень "алгоритмически" как мне кажется. :) И срез используется один раз. Я в комментарии сказал что взятие среза - дополнительная память. Приврал слегка. Не всегда это так. Если срез слева от присваивания, дополнительная память не будет использоваться.

P.P.S. Если преподавателя не слушать, то каноническое решение такое:

n = int(input('Enter the size: '))
array = [int(input('Enter an element: ')) for _ in range(n)]
array = list(set(array))
print(array)

Сложность этого решения и по времени и по памяти - O(N).

Решение с сортировкой потребует O(NlogN) времени (N - длина исходного массива) и, скорее всего, O(N) дополнительной памяти при сортировке. Но сортировку можно заменить на другую, которая не использует дополнительную память.

БЛОГ НА HUSL

Алгоритмическое решение задачи на удаление повторяющихся элементов в одномерном массиве

Ответы (1 шт):