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

Ответ 1

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

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

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

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

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

Поскольку некоторые комментаторы возмущены тем, что я не включил все детали того, как найти цикл в связанном списке, вот он. Нет promises, что это не багги (это псевдокод 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).

Ответ 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;
}

Ответ 3

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

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

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

Ответ 4

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

cout<<i;

Ответ 5

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

Объяснение:

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

Algo:

• Начиная с последнего node (a[n+1]) найдите meet node с помощью указателей slow (1x) и fast (2x).
• Передвиньте два указателя (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