Головоломка: поиск повторяющегося элемента в массиве

Question

Размер массива равен n. Все элементы в массиве различаются в диапазоне от [0, n-1], за исключением двух элементов. Обратите внимание на повторяющийся элемент без использования дополнительного временного массива с постоянной временной сложностью.

Я пробовал с o (n) следующим образом.

a[]={1,0,0,2,3}; 
    b[]={-1,-1,-1,-1,-1}; 
    i=0; 
    int required; 
    while(i<n) 
    { 
     b[a[i]]++; 
     if(b[a[i]==1) 
     required=a[i]; 
    } 
    print required; 

Если нет никаких ограничений на диапазон чисел позволяет т.е. вне диапазона also.Is возможно Get O (N) раствор без временного массива.

Answer 1

1. Посмотрите, что первый и последний номер
2. Вычислить SUM (1) элементов массива без дубликата (как вы знаете, что сумма 1 ... 5 = 1 + 2 + 3 + 4 + 5 = 15 Назовите его SUM (1)). Как указывал AaronMcSmooth, формула равна Sum(1, n) = (n+1)n/2.
3. Рассчитайте SUM (2) элементов в массиве, которые вам даны.
4. Вычесть SUM (2) - SUM (1). Вау! В результате получается дублирующее число (например, если данный массив равен 1, 2, 3, 4, 5, 3, SUM (2) будет 18. 18 - 15 = 3. Таким образом, 3 является дубликатом).

Коды удачи!

Answer 2

Lazy solution: Поместите элементы в java.util.Set по одному add(E) до получения add(E) == false.

Извините, нет постоянного времени. HashMap: O (N), TreeSet: O (lgN * N).

Answer 3

Выберите два разных случайных индекса. Если значения массива в этих индексах одинаковы, верните true.

Это работает в постоянное время. В качестве бонуса вы получите правильный ответ с вероятностью 2/n * 1/(n-1).

Answer 4

Постройте таблицу поиска. Погляди. Готово.

Non-временное решение массива:

Сложение поиска в аппаратных средствах ворота массива, вызовите.

Answer 5

XOR все элементы вместе, затем XOR результат с XOR([0..n-1]).

Это дает вам missing XOR repeat; начиная с missing!=repeat, по меньшей мере один бит устанавливается в missing XOR repeat.

Выберите один из этих битов. Итерации по всем элементам снова, и только XOR элементов с этим набором бит. Затем итерации от 1 до n-1 и XOR те числа, у которых этот бит установлен.

Теперь это либо повторяющееся значение, либо отсутствующее значение. Сканирование элементов для этого значения. Если вы его найдете, это повторяющийся элемент. В противном случае это недостающее значение, поэтому XOR оно с missing XOR repeat.

Answer 6

O (n) без временного массива.

a[]={1,0,0,2,3}; 
i=0; 
int required; 
while(i<n) 
{ 
    a[a[i] % n] += n; 
    if(a[a[i] % n] >= 2 * n) 
    required = a[i] % n; 
} 
print required; 

(при условии, конечно, что п < MAX_INT - 2n)

Answer 7

Лучшее, что я могу сделать, это O(n log n) во времени и O(1) в пространстве:

Основная идея заключается в том, чтобы выполнить бинарный поиск значения0 через n-1, передавая весь массив n элементов на каждом шагу.

1. Первоначально, пусть i=0, j=n-1 и k=(i+j)/2.
2. При каждом прохождении через массив суммируйте элементы, значения которых находятся в диапазоне от i до k, и подсчитайте количество элементов в этом диапазоне.
3. Если сумма равна (k-i)*(k-i+1)/2 + i*(k-i+1), то диапазон i по k не имеет ни дубликата, ни пропущенного значения. Если количество элементов меньше k-i+1, тогда диапазон имеет опущенное значение, но не дубликат. В любом случае замените i на k+1 и k на новое значение (i+j)/2.
4. Else, заменить j на k и k на новое значение (i+j)/2.
5. Если i!=j, Гото 2.

Алгоритм завершается i==j и оба равны дублированного элемента.

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

Answer 8

Основано на ответе @ sje. Худший случай - 2 прохода через массив, без дополнительного хранения, без разрушения.

O (n) без временного массива.

a[]={1,0,0,2,3}; 
i=0; 
int required; 
while (a[a[i] % n] < n)    
    a[a[i++] % n] += n; 

required = a[i] % n; 
while (i-->0) 
    a[a[i]%n]-=n; 

print required; 

(при условии, конечно, что п < MAX_INT/2)

Answer 9

Этот пример может быть полезен для Int, полукокса, и строки.

char[] ch = { 'A', 'B', 'C', 'D', 'F', 'A', 'B' }; 
Dictionary<char, int> result = new Dictionary<char, int>(); 
foreach (char c in ch) 
{ 
    if (result.Keys.Contains(c)) 
    { 
     result[c] = result[c] + 1; 
    } 
    else 
    { 
     result.Add(c, 1); 
    } 
} 
foreach (KeyValuePair<char, int> pair in result) 
{ 
    if (pair.Value > 1) 
    { 
     Console.WriteLine(pair.Key); 
    } 
} 
Console.Read();