4
def A(number) :

    for item in range(len(number)) :
        if number.count(item) < 2 : # определяю уникальный или нет
            number[item] *= 0       # превращаю уникальный в ноль

            for i, elem in enumerate(number) :
                if elem == 0 :
                    del number[i]    # если ноль - удаляю
                    return number

Дан непустой массив целых чисел. Нужно вернуть массив, состоящий только из неуникальных элементов данного массива. Для этого необходимо удалить все уникальные элементы (которые присутствуют в данном массиве только один раз). Нельзя менять оригинальный порядок элементов.

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

Если дается [1, 2, 3, 3, 3] , то должно вернуться - [3, 3, 3]. А у меня возвращается - [2, 3, 3, 3].

2

3 ответа 3

7

Линейный алгоритм по времени и памяти (O(n) - время, O(n) - память), который новый список возвращает, содержащий элементы, которые встречаются более одного раза, сохраняя порядок исходного списка:

from collections import Counter

def non_uniq(numbers):
    counter = Counter(numbers)
    return [n for n in numbers if counter[n] > 1]

Пример из вопроса:

>>> non_uniq([1, 2, 3, 3, 3])
[3, 3, 3]

Если одинаковые элементы всегда рядом, можно однопроходный алгоритм, использующий только постоянную память (O(n) - время, O(1) - память):

from itertools import groupby, islice

def non_uniq_adjacent(sorted_numbers, min_repeat=2):
    for _, same in groupby(sorted_numbers):
        adjacent = list(islice(same, min_repeat))
        if len(adjacent) == min_repeat:
            yield from adjacent
            yield from same

Пример:

>>> list(non_uniq_adjacent([1, 2, 3, 3, 3]))
[3, 3, 3]
1

Вот в этом куске

for i, elem in enumerate(number) :
    if elem == 0 :
        del number[i]    # если ноль - удаляю

Вы удаляете элементы из того списка, по которому итерируетесь. Так делать нельзя, иначе после удаления элемента цикл будет перескакивать через следующий элемент (потому что после удаления предыдущего он сдвинулся на его место).

Поэтому некоторые элементы у вас и не удаляются - в цикле они просто проскальзывают мимо.

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

Например, вашу функцию можно написать в одну строчку:

def A(number) :
  return [i for i in number if number.count(i) > 1]
3
  • пожалуйста, не предлагайте квадратичный алгоритм вместо линейного, если заранее неизвестно что ввод маленький или по меньшей мере упомяните явно O(n**2), особенно в ответе на простой вопрос, когда люди могут не осознавать big O операций типа number.count(i).
    – jfs
    Commented 30 янв. 2017 в 21:17
  • @jfs, согласен, алгоритм не оптимален. Но я просто лаконично переписал тот же алгоритм, который у автора и так был.
    – Xander
    Commented 30 янв. 2017 в 21:29
  • 2
    в вопросе код сломанный, поэтому как для самого автора так и для людей с похожей проблемой приземлившихся здесь из поисковика (сайт в основном для второй категории людей существует—иначе и ответы и разрешённые вопросы были бы другие), следует упомянуть если в коде есть очевидные вам проблемы (тем более что если нет специальных потребностей, то есть простое решение в две строчки). Я в конце ответа проиллюстрировал разницу между линейным и квадратичным алгоритмом
    – jfs
    Commented 30 янв. 2017 в 22:38
1

collections.Counter

from collections import Counter
def A(numbers: list) -> list:
    '''Нужно вернуть массив, состоящий только из неуникальных элементов данного массива.
    Для этого необходимо удалить все уникальные элементы'''
    counter = Counter(numbers)
    unique = [n for n in counter if counter[n] == 1]  # уникальные элементы
    for n in unique:  # удалить все уникальные элементы
        numbers.remove(n)
    return numbers
2

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.