Найдите число, где это появляется точно времена N/2

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

Я считаю, что проблему можно переформулировать так: «Найти число, которое встречается более одного раза».

В самом худшем случае нам нужно было бы пройти еще немного чем половина списка (1 + N / 2), прежде чем мы нашли 2-й экземпляр неуникального числа.

Пример наихудшего случая: array [] = {1, 2, 3, 4, 5, 10, 10, 10, 10, 10}

В среднем по , хотя мы Нужно только повторить 3 или 4 элемента, так как половина элементов будет содержать неуникальное число, то есть примерно любое другое число.

Примеры идеально равномерного распределения:

• array [] = {1, 10, 2, 10, 3, 10, 4, 10, 5, 10}
• array [ ] = {10, 1, 10, 2, 10, 3, 10, 4, 10, 5}

Другими словами, даже если N = 1 миллион, вам все равно потребуется только поиск; в среднем первые 3 или 4 элемента до того, как вы обнаружили дубликат.

Что такое большая запись O для фиксированного / постоянного времени выполнения, которое не увеличивается с N?

Код:

int foundAt = -1;

for (int i=0; (i<N) && (foundAt==-1); i++)
{
    for (int j=i+1; j<N; j++)
    {
        if (array[i] == array[j])
        {
             foundAt = i;
             break;
        }
     }
}

int uniqueNumber = array[foundAt];

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

Я думаю, что это O (n), поэтому я думаю, что это не очень помогает.

Это кажется слишком простым, поэтому я думаю, что не правильно понимаю проблему.

Восстановление моего решения из комментария к версии Ганеша, чтобы я мог отформатировать его:

for (i=0; i<N-2; i+=3) { 
   if a[i] == a[1+1] || a[i] == a[i+2] return a[i];
   if a[i+1] == a[i+2] return a[i+1]; 
} 
return a[N-1]; // for very small N

Вероятность выигрыша после 1 итерации: 50%

Вероятность выигрыша после 2 итераций: 75 %

и т. Д.

В худшем случае, O (n) время O (1) пространство.

Обратите внимание, что после N / 4 итераций вы использовали все N / 2 уникальных чисел, поэтому этот цикл никогда не будет проходить через более чем 3/4 массива, если он соответствует указанному.

Довольно просто увидеть, что алгоритма O (log n) не существует. Очевидно, что вам нужно взглянуть на элементы массива, чтобы выяснить, какой элемент повторяется, но независимо от того, в каком порядке вы выбираете элементы, элементы первого этажа (n / 2), которые вы просматриваете, могут быть уникальными. Вы могли бы просто быть неудачником. Если бы это произошло, у вас не было бы возможности узнать, какой элемент повторяется. Поскольку ни один алгоритм, который использует ссылки на массив меньше, чем floor (n / 2) или меньше, не будет работать, сублинейный алгоритм определенно не существует.

Мой ответ был:

1. Разделите N элементов на части [N / 3] (т.е. каждая часть будет иметь 3 элемента.
2. Теперь сравните эти 3 элемента между собой. - 3 сравнения
3. По крайней мере одна часть будет иметь две копии одного и того же элемента. Отсюда и число.

Время выполнения - O (N)

Вы не можете сделать это в сублинейное время, потому что вам нужно прочитать массив. Для обработки массива из миллиона записей за логарифмическое время потребуется только чтение ~ 20 (log2) элементов - это явно невозможно. В конце концов, если вы предполагаете, что первый найденный дубликат повторяется N / 2 раза, это все равно O (n), потому что вам может понадобиться просмотреть 500 001 элементов, чтобы найти дубликат.

Вы можете сделать это в O (n), если предположите, что целые числа неотрицательны. Это выглядит следующим образом (псевдо-Java):

int repeatedNumber = -1; // sentinel value
int count = 0;
BitSet bits = new BigSet(); // this bitset needs to have 2^31 bits, roughly 2.1 billion
boolean duplicate = false;
for (int i : elements) {
  if (bits[i].isSet()) {
    if (repeatedNumber == -1) {
      repeatedNumber = i;
      count = 1;
    } else if (i == repeatedNumber) {
      count++;
    } else {
      System.out.println("Array has more than one repeated element");
      duplicate = true;
      break;
    }
  } else {
    bits[i].set();
  }
}
if (!duplicate && repeatedNumber != -1 && count == elements.length/2) {
  System.out.println(repeatedNumber + " occurred " + count + " times. The rest of the elements are unique");
} else {
  System.out.println("Not true");
}

Подобный метод используется для сортировки массива уникальных целых чисел в O (n) (радикальная сортировка).

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

Предположим, что алгоритм наихудшего журнала (n) существует. Этот алгоритм обращается к массиву не более log (n) раз. Поскольку он не может делать предположения о том, какие элементы находятся, где я могу выбрать, какие элементы log (n) он видит. Я выберу первый лог (n) уникальных элементов. Он еще не нашел дубликат, и до сих пор существуют n / 2 - log (n) уникальные элементы для меня, чтобы кормить его в случае необходимости. На самом деле, я не могу быть вынужден кормить его дублированным номером, пока он не прочитает n / 2 элемента. Поэтому такой алгоритм не может существовать.

С чисто интуитивной точки зрения это просто кажется невозможным. Log (4 миллиарда) - это 32. Так что с массивом из 4 миллиардов чисел, 2 миллиарда из которых уникальны, в произвольном порядке, есть способ найти дублированный элемент, проверяя только 32 элемента?

Это плохой вопрос для собеседования.

1. Вы сами не знаете ответа.
2. В нем нет любое экономическое обоснование, стоящее за этим, поэтому вам будет трудно объяснить его кандидату.

В основном из-за первого. Что вы ищете? Что кандидат должен предложить решение O (log n), о существовании которого вы не знаете? Если вам нужно спросить StackOverflow, можно ли ожидать, что кандидат об этом придет на собеседовании?

Предположим, у вас есть такой алгоритм Python:

import math
import random

def find_duplicate(arr, gap):
    cost, reps = 0, 0
    while True:
        indexes = sorted((random.randint(0,len(arr)-i-1) for i in xrange(gap)), reverse=True)
        selection = [arr.pop(i) for i in indexes]
        selection_set = set(selection)
        cost += len(selection)
        reps += 1
        if len(selection) > len(selection_set):
            return cost, reps

Идея состоит в том, что arr - это ваш набор значений, а пробел - база журнала -2 размера. Каждый раз, когда вы выбираете элементов промежутка и смотрите, есть ли повторяющиеся значения. Если да, верните вашу стоимость (в подсчете проверенных элементов) и количество итераций (где вы проверяете элементы log2 (размер) на итерацию). В противном случае посмотрите на другой набор размеров пробелов .

Проблема с тестированием этого алгоритма состоит в том, что создание данных каждый раз в цикле и изменение данных является дорогостоящим, предполагая, что большой объем данные. (Первоначально я делал 1 000 000 элементов с 10 000 000 итераций.)

Итак, давайте сведем к эквивалентной задаче. Данные передаются в виде n / 2 уникальных элементов и n / 2 повторяющихся элементов. Алгоритм выбирает случайные индексы элементов log2 (n) и проверяет наличие дубликатов. Теперь нам даже не нужно создавать данные и удалять проверенные элементы: мы можем просто проверить, есть ли у нас два или более индексов на полпути . Выберите индексы пробелов , проверьте наличие 2 или более на половине пути: верните, если найдено, в противном случае повторите.

import math
import random

def find_duplicate(total, half, gap):
    cost, reps = 0, 0
    while True:
        indexes = [random.randint(0,total-i-1) for i in range(gap)]
        cost += gap
        reps += 1
        above_half = [i for i in indexes if i >= half]
        if len(above_half) >= 2:
            return cost, reps
        else:
            total -= len(indexes)
            half -= (len(indexes) - len(above_half))

Теперь введите код следующим образом:

if __name__ == '__main__':
    import sys
    import collections
    import datetime
    for total in [2**i for i in range(5, 21)]:
        half = total // 2
        gap = int(math.ceil(math.log10(total) / math.log10(2)))
        d = collections.defaultdict(int)
        total_cost, total_reps = 0, 1000*1000*10
        s = datetime.datetime.now()
        for _ in xrange(total_reps):
            cost, reps = find_duplicate(total, half, gap)
            d[reps] += 1
            total_cost += cost
        e = datetime.datetime.now()
        print "Elapsed: ", (e - s)
        print "%d elements" % total
        print "block size %d (log of # elements)" % gap
        for k in sorted(d.keys()):
            print k, d[k]
        average_cost = float(total_cost) / float(total_reps)
        average_logs = average_cost / gap
        print "Total cost: ", total_cost
        print "Average cost in accesses: %f" % average_cost
        print "Average cost in logs: %f" % average_logs
        print

Если вы попробуете этот тест, вы найдете что количество раз, когда алгоритм должен выполнять множественный выбор, уменьшается с увеличением количества элементов в данных. То есть ваша средняя стоимость в журналах асимптотически приближается к 1 .

elements    accesses    log-accesses
32          6.362279    1.272456
64          6.858437    1.143073
128         7.524225    1.074889
256         8.317139    1.039642
512         9.189112    1.021012
1024        10.112867   1.011287
2048        11.066819   1.006075
4096        12.038827   1.003236
8192        13.022343   1.001719
16384       14.013163   1.000940
32768       15.007320   1.000488
65536       16.004213   1.000263
131072      17.002441   1.000144
262144      18.001348   1.000075
524288      19.000775   1.000041
1048576     20.000428   1.000021

Является ли это аргументом в пользу того, что идеальным алгоритмом является log2 (n) в среднем случае ? Возможно. Конечно, в худшем случае это не так.

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

Если я правильно понимаю проблему: все, что мы знаем о массиве, это его длина, и он имеет (N / 2) +1 уникальных элемента, где 1 элемент повторяется N / 2 раза (в произвольном порядке).

Я думаю, что это имеет жесткий предел O (N) для решения, поскольку вы не можете действительно утверждать (для общего массива), что вы нашли число без найти хотя бы 2 одинаковых числа. Я не думаю, что существует поиск неупорядоченного массива, который может обнаружить дубликат в O (logN) (поправьте меня, если я ошибаюсь). В худшем случае вам всегда нужно будет прочитать как минимум N / 2 +1 элементов.

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

Edit. вам нужно будет прочитать n / 2, чтобы доказать, что такое число существует, но если вы знали, что число существует, и хотели только его найти, вы могли бы прочитать образцы sqrt (n)

Вы должны записать данные конфигурации конкретного пользователя в папку Application Data для текущего пользователя, используя специальные папки enum и Enivronment.GetFolderPath .

Это был бы довольно паршивый вопрос для собеседования. Часто задаются похожие, менее паршивые вопросы, на которые часто получают неверные ответы, и часто неправильно запоминаются неудачными кандидатами. Например, типичный вопрос может заключаться в том, что, учитывая массив из N элементов, не зная , есть ли элемент большинства, определить, есть ли один элемент и какой именно, за время O (N) и O (1) вспомогательное пространство (так что вы не можете просто настроить хеш-таблицу или что-то еще для подсчета вхождений разных значений). "Мур"

Я думаю, вам просто нужно проанализировать массив, сохранив отставание из двух элементов. Поскольку N / 2 равны, а остальные гарантированно различны, в вашем массиве должно быть одно место i, где

a [i] == a [i-1] OR a [i] == a [i- 2]

выполните итерацию один раз по вашему массиву, и вы получите сложность примерно 2 * N, которая должна быть внутри O (N).

Этот ответ в некоторой степени похож на ответ Ганеша М. и Дуги, но я думаю, что немного проще.

Питер совершенно прав. Вот более формальный способ переформулировать его доказательство:

Пусть множество S будет множеством, содержащим N элементов. Это объединение двух наборов: p, который содержит символ α, повторяющийся N / 2 раза, и q, который содержит N / 2 уникальных символа ω ₁ .. ω _{n / 2} . S = p ∪ q.

Предположим, существует алгоритм, который может обнаружить ваше дублированное число в сравнениях log (n) в худшем случае для всех N> 2. В худшем случае означает, что не существует подмножество r ⊂ S такое, что | r | = log ₂ N, где α ∉ r .

Однако, поскольку S = p ∪ q, имеется | p | много элементов ≠ α в S. | p | = N / 2, так что ∀ N / 2 такое, что N / 2 ≥ log ₂ N, должно существовать хотя бы одно множество r ⊂ S такое, что | r | = log ₂ N и α r. Это так для любого N ≥ 3. Это противоречит сделанному выше предположению, поэтому такого алгоритма быть не может.

QED.

Вот Ответ Дон Йохэ в Ruby:

#!/usr/bin/ruby1.8

def find_repeated_number(a)
  return nil unless a.size >= 3
  (0..a.size - 3).each do |i|
    [
      [0, 1],
      [0, 2],
      [1, 2],
    ].each do |j1, j2|
      return a[i + j1] if a[i + j1] == a[i + j2]
    end
  end
end

p find_repeated_number([1, 1, 2])   # => 1
p find_repeated_number([2, 3, 2])   # => 1
p find_repeated_number([4, 3, 3])   # => 1

O (n)