Разделяй и властвуй алгоритм, чтобы найти один элемент, который не повторяется - PullRequest
Новая
       6

Разделяй и властвуй алгоритм, чтобы найти один элемент, который не повторяется

0 голосов
/ 07 октября 2019

Если у меня есть отсортированный список целых чисел, где каждый элемент, кроме одного, повторяется, как бы я нашел одноэлементный элемент менее чем за O (n) времени?

Например: (−2, −2, 5, 5, 5, 67, 67, 72, 80, 80, 80, 80) вернет 72.

Я вполне уверен, что бинарный поиск вовлечен в это, но не уверен, как его реализовать,Я просто ищу здесь псевдокод.

Я думаю перебрать список и выполнить двоичный поиск последнего вхождения текущего элемента. Если его индекс совпадает с индексом, на котором мы сейчас находимся, это единственный элемент. Если нет, продолжай. Это было бы O (nlogn), я думаю.

Ответы [ 2 ]

1 голос
/ 07 октября 2019

Если каждое целое число может повторяться произвольное количество раз, лучшим алгоритмом будет O(n), поскольку нет способа избежать повторения каждого целого числа. Просто перебирайте список и держите счетчик того, сколько одинакового целого числа было найдено в строке. Если счетчик только один и новое целое число обнаружено, то завершите работу, поскольку мы нашли неповторяющееся целое число.

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

0 голосов
/ 07 октября 2019

O (n) реализация Python: 

def find_singletons(items):
    singletons = []
    a, b = items[:2]
    for item in items[2:]:
        if a != b and b != item:
            singletons.append(b)
        a, b = b, item
    return singletons


items = [-2, -2, 5, 5, 5, 67, 67, 72, 80, 80, 80, 80]
print(find_singletons(items))
# [72]

Другая O (n) реализация Python (с использованием счетчика): 

def find_singletons2(items):
    singletons = []
    count = 1
    last_item = items[0]
    for item in items[1:]:
        if last_item != item:
            if count == 1:
                singletons.append(last_item)
            count = 1
        else:
            count += 1
        last_item = item
    return singletons


items = [-2, -2, 5, 5, 5, 67, 67, 72, 80, 80, 80, 80]
print(find_singletons(items))
# [72]
...