Почему не работает поиск уникального числа в списке?

Question

[EvgenySE]

Задача найти уникальное число в списке.
К примеру:
find_uniq([ 1, 1, 1, 2, 1, 1 ]) == 2

Изначально, я написал следующий код:

def find_uniq(arr):
    x = sorted(arr)
    if x[0] == x[1]:
        return x[-1]
    elif x[0] > x[1]:
        return x[0]
    else:
        return []

Но он подходит для целых положительных чисел. Если они отрицательные или как положительные так и отрицательные, то метод сравнения не подходит.

Потом я написал следующий код:

arr = [-1, -2, -1, -1]
for i in range(arr[0], arr[-1]):
    while i[0] == i[-1]: # я перебираю крайние значения списка с помощью цикла</i>
        arr.remove([0]) # если они равны, то я сокращаю его на проверенные уже крайние значения</i>
        arr.remove([-1])
        if i[0] != i[-1]: # если нахожу несоответствия, то значит одно из двух чисел уникальное.</i>
            break
            print(i[0], i[-1])
        else:
            continue

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

Answer 1

[Vindicar]

Пропускаешь свой список через Collections.Counter, получишь число вхождений каждого элемента.
Потом ищешь элементы, у которых число вхождений равно 1.

А если хочешь именно циклом, то можно так:

def find_uniqs(arr):
    uniqs = set()
    srtd = sorted(arr)  # список идёт по возрастанию
    for i in range(1, len(srtd)-1):
        # если элемент не равен соседям, то он один такой в списке
        if srtd[i-1] != srtd[i] and srtd[i] != srtd[i+1]:
            uniqs.add(srtd[i])
    # обрабатываем края списка, если они есть, т.е. список из >1 элемента
    if len(srtd) > 1:
        if srtd[0] != srtd[1]:
            uniqs.add(srtd[0])
        if srtd[-1] != srtd[-2]:
            uniqs.add(srtd[-1])
    elif srtd: # у нас один элемент в списке?
        uniqs.add(srtd[0]) # ну тогда его и добавляем.
    return uniqs

Comments

[EvgenySE]

Спасибо! Отдельно благодарю за то, что прислушались к моей просьбе остаться в рамках ЦИКЛА! Решение правильное, но в конце немного подкорректировал, чтобы можно было осуществить проверку.

uniqs = list(uniqs)
    return uniqs[0]

[Vindicar]

EvgenySE, ну твоя коррекция имеет смысл, если ты уверен, что у тебя будет одно и только одно уникальное число в списке. Я исходил из того, что их может быть ноль или несколько.

Answer 2

[Алан Гибизов]

Попробуйте по-другому. Получите уникальные элементы списка посредством множества (set) и затем посредством метода .count() для списка посчитайте, сколько раз встречается каждый уникальный элемент из множества в вашем списке. Элементы, для которых .count вернёт 1, и есть уникальные.

def print_unic_elements(arr):
    [print(i) for i in set(arr) if arr.count(i) == 1]

Comments

[profesor08]

Зачем Set, если можно просто посчитать?

[Алан Гибизов]

profesor08, set - чтобы получить множество уникальных значений, количество вхождений которых надо считать.
А вы напишите свой вариант ответа без set, и мы с удовольствием ознакомимся и поучимся; я - так точно, безо всякого сарказма.

[profesor08]

Алан Гибизов, не нужная операция по вычленению уникальных чисел. Достаточно пройтись по массиву и сосчитать числа, а результаты куда-то записать.

[Алан Гибизов]

profesor08, вы код примера приведите, пожалуйста, а то я не понимаю, к сожалению, как это сделать.

[profesor08]

Алан Гибизов, а что конкретно не понятного?

[Алан Гибизов]

profesor08, я посмотрел ваш код. Привожу сравнение, насколько ваш код медленнее, больше и хуже читается:

from random import randint
from time import time
arr = [randint(1, 3) for _ in range(1000000)]
arr.append(4)


def profesor08(arr):
    counter = dict();
    for n in arr:
        if str(n) in counter:
            counter[str(n)] = counter[str(n)] + 1
        else:
            counter[str(n)] = 1
    
    for (key, value) in counter.items():
        if value == 1:
            print(key)


def phaggi(arr):
    for i in set(arr):
        if arr.count(i) == 1:
            print(i)


starttime = time()
profesor08(arr)
firsttime = time() - starttime

starttime = time()
phaggi(arr)
secondtime = time() - starttime

print(f"professor's time:\t{firsttime*100}\nphagocyte's time:\t{secondtime*100}")

Вот поэтому вариант с set лучше.

[Алан Гибизов]

А можно и так:

def phaggi(arr):
    [print(i) for i in set(arr) if arr.count(i) == 1]

[profesor08]

Алан Гибизов, на прекрасно подготовленных данных преимущество вашего кода очевидно. Но на более разбросанных, мой пример веселее.

arr = [randint(1, 1000) for _ in range(100000)]
arr.append(999999)

999999
999999
professor's time:	8.379292488098145
nphagocyte's time:	239.41876888275146

[Алан Гибизов]

profesor08, простите, но вы же сами подготовили те самые "прекрасные" данные - я просто добавил количество элементов списка.

Теперь вы меняете исходные данные и утверждаете, что теперь-то ваш вариант выигрышный. Т.е. ВАШ вариант теперь выигрывает на вновь СПЕЦИАЛЬНО ПОДГОТОВЛЕННЫХ ДАННЫХ.
Переобуваетесь на ходу...

В то же время, нельзя не признать, что для случаев, похожих на новый вариант данных, ваш вариант быстрее.

[profesor08]

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

[Алан Гибизов]

profesor08, не соглашусь. Заранее посчитать результат можно, если заранее знаете ответ. Достаточно добавить немножно рандома в число (или числа), которые мы append-им, и всё пропало :)

Что можно сказать по результатам:
для определенного класса задач быстрее один способ, для другого - другой способ. В этом ничего необычного нет.

У нас есть задача, в ней приведен пример, и ничего не сказано, что данные могут быть сильно другой структуры. Вы также привели пример, аналогичный примеру в задаче, и ничего не сказали, что данные могут быть другой структуры. На примере из задачи и на вашем первом примере мой алгоритм быстрее. Это неоспоримо.

В принципе, можно оценить примерно диапазоны применимости обоих алгоритмов и сделать универсальную функцию для любых диапазонов :)
Полагаю, более конструктивного решения не найти. Давайте остановим разгорающийся флейм.

[profesor08]

Алан Гибизов, все зависит от разнообразия элементов.

[Алан Гибизов]

profesor08, неоспоримо. Я прикинул, что до 40 разных элементов set быстрее; дальше начинает проигрывать. Добавление количества уникальных элементов снижает эту границу. От общего количества элементов в arr зависимости не нашел.

Answer 3

[Константин Нагибович]

Создай словарь. Ключ словаря - число, а значение - количество повторений этого числа. Перебираешь свой список, заполняешь словарь и все.

Answer 4

[profesor08]

arr = [1,2,2,1,2,1,3,2,1,2,3,4]
counter = dict();

for n in arr:
    if str(n) in counter:
        counter[str(n)] = counter[str(n)] + 1
    else:
        counter[str(n)] = 1

for (key, value) in counter.items():
    if value == 1:
        print(key)