Найти любое из нескольких возможных повторяющихся целых чисел в списке

Question

Учитывая массив из n+1 целых чисел, каждое в диапазоне от 1 до n, найдите целое число, которое повторяется.

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

top = 0;
bot = 0;
for i=1:n+1
  if P[i] > n/2 
    top = top+1;
  else
    bot = bot+1;
end

Итак, я утверждаю, что один из них, top или bot, долженбыть больше, чем n/2 PhP снова.Возьмите этот диапазон и повторите.

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

Answer 1

Я не уверен, как вы определяете «лучше», но, возможно, это подходит. По крайней мере, оно отличается от вашего решения и решений вопросов из связанного списка (каламбур).

Если мы сделаем путь

n+1 --> array[n+1] --> array[array[n+1]] --> ...

тогда этот путь содержит цикл тогда и только тогда, когда array^k[n+1] = array^l[n+1] для некоторого k != l, то есть, если и только если есть повторение. Теперь этот вопрос становится общей проблемой связанного списка, которую можно решить следующим образом.

Запустите две частицы на первом узле. Пусть первая частица движется с удельной скоростью, а вторая частица с удвоенной скоростью. Тогда, если есть цикл, вторая частица в конечном итоге будет возвращаться назад за первой, и в конце концов они будут такими же. Зачем? Что ж, если вы думаете о частицах как о круге (который они когда-то найдут в цикле), то в каждой единице времени вторая частица приближается на один шаг ближе к первой. Поэтому они должны в конечном итоге столкнуться. Тот, который они делают, вы нашли петлю. Чтобы найти повторяющееся значение, просто получите длину цикла, оставив одну частицу неподвижной, пока другая снова запускает цикл. Затем снова запустите обе частицы в начале, позвольте одному переместить длину цикла вперед, а затем направьте обе частицы вместе с постоянным расстоянием между ними, пока они не встретятся снова в начале цикла.

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

%% STEP 1: find a point in the cycle of the linked list using a slow and fast particle
slow = n+1;
fast = n+1;
for i=1 to n+1
    slow = array[slow];
    fast = array[array[fast]];
    if (slow == fast)
        break;
end

%% STEP 2: find the length of the cycle by holding one particle fixed
length = 1;
fast = array[fast]
while fast != slow
    fast = array[fast];
    length = length+1;
end

%% STEP 3: find the repeated element by maintaining constant distance between particles
slow = n+1;
fast = n+1;
for i=1 to length
    fast = array[fast];
end
while fast != slow
    fast = array[fast];
    slow = array[slow];
end

%% STEP 4: return the repeated entry
return slow;

Здесь я начал с n+1, поскольку array[i] находится между 1 и n, поэтому ни одна частица никогда не будет отправлена ​​обратно на n+1. Это делает не более одного прохода через массив (хотя и не по порядку) и отслеживает две частицы (медленную и быструю) и одно целое число (длину). Следовательно, пробел равен O (1), а время - O (n).

Answer 2

Если вы знаете, что существует ровно одно дублирующееся число, вы можете найти его, сложив их все и вычтя сумму чисел от 1 до n:

duplicate = sum P[i] - n(n+1)/2

Если нет, то вы можете перебирать массив и помещать каждое число в хеш-таблицу. Если номер уже существует, то это дубликат. Это также O (n), если предположить, что операции хеширования O (1).

Или событие лучше - чтобы избежать хеш-таблицы, вы можете использовать массив логических значений размера n:

int[] P = new int[] { 3, 2, 5, 1, 4, 2 };
bool[] Q = new bool[6];

foreach( var p in P ){
    if ( Q[p] ) {
        Console.WriteLine("Duplicate: " + p);
        break;
    }
    Q[p] = true;
}

Answer 3

Мы используем обнаружение окружности * Идея 1002 * для решения этой проблемы.

Все, что нам нужно сделать, это сначала найти начало круга и затем найти дубликат в круге.

Вот код на С ++:

int findDuplicate(vector<int>& nums) {
    int slow = nums[0];
    int fast = nums[nums[0]];

    while(slow != fast){
        slow = nums[slow];
        fast = nums[nums[fast]];
    }
    fast = 0;
    while(slow != fast){
        slow = nums[slow];
        fast = nums[fast];
    }

    return slow;
}

Answer 4

Это работает так же, как ответ @ PengOne, но я считаю, что это проще.

Пояснение:

При таком подходе массив обрабатывается как граф, в котором значение индекса i указывает на индекс a[i]-1 (поэтому значение 1 указывает на индекс 0). Существует как минимум 1 повторяющееся число, поэтому график будет циклическим. Существует n+1 элементов, а максимальное значение равно n, поэтому последний узел a[n+1] никогда не будет частью цикла, а войдет в цикл. Это важно, так как этот последний узел является start node для обхода. Обратите внимание, что если узел, являющийся частью цикла, используется как start node с указателями slow (1x) и fast (2x), то они встречаются на том же самом узле, что бесполезно. Давайте назовем сходящийся узел как meet node. Если meet node составляет k прыжков от cycle node, start node также будет k прыжков от cycle node. Эта логика аналогична нахождению узла цикла в циклически связанном списке. Массив пересекается максимум 3 раза, поэтому O(n) время и O(1) пробел.

Algo:

1. Начиная с последнего узла (a[n+1]), найдите meet node, используя указатели slow (1x) и fast (2x).
2. Продвиньте два указателя (1x) с meet node и с start node, и они сойдутся в cycle node (повторяющиеся числа указывают на cycle node).

Код:

//pseudocode
//O(n) time, O(1) space
findrepeating(a):
    x = findrepeating(a, findmeet(a), a[a.length() -1])
    return x

findmeet(a):
    slow = fast = a[a.length() -1]
    while true:
        slow = a[slow-1]
        fast = a[a[fast-1]-1]
        if slow == fast:
            break
    meet = slow // or fast
    return meet

findrepeating(a, meet, start):
    m = meet
    s = start
    while m != s:
        m = a[m-1]
        s = a[s-1]
    return m // or s

Answer 5

for(int i=n+1;i!=a[i];i=a[i]);

cout<<i;

Answer 6

Как насчет этого простого решения:

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

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