Найти повторяющийся элемент в массиве

Question

Рассмотрит массив INT положительных чисел:

{1,3,6,4,7,6,9,2,6,6,6,6,8} 

Дано: только один номер повторяется, номер возврата и позиция с эффективным алгоритмом.

Любые идеи для эффективных алгоритмов?

Answer 1

Хеш будет прекрасно работать здесь. Добавьте номера к нему один за другим, каждый раз проверяя, что номер уже там.

Answer 2

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

Answer 3

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

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

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

Answer 4

Я хотел бы попробовать это:

1. все вязы из списка должны быть рассмотрены (цикл => по списку)
2. перед повторен вяз известно, магазин вяз => местоположение/индекс в хеш-словаре
3. , как только будет обнаружено второе появление повторяющегося элемента, сохраните его первое положение (из хэша) и текущую позицию в массиве результатов
4. сравните дополнительные вяза списка с повторным вязом , добавьте найденные местоположения в массив результатов

в коде:

Function locRep(aSrc) 
    ' to find repeated elm quickly 
    Dim dicElms : Set dicElms = CreateObject("Scripting.Dictionary") 
    ' to store the locations 
    Dim aLocs : aLocs  = Array() 
    ' once found, simple comparison is enough 
    Dim vRepElm : vRepElm  = Empty 
    Dim nIdx 
    For nIdx = 0 To UBound(aSrc) 
     If vRepElm = aSrc(nIdx) Then ' repeated elm known, just store location 
     ReDim Preserve aLocs(UBound(aLocs) + 1) 
     aLocs(UBound(aLocs)) = nIdx 
     Else ' repeated elm not known 
     If dicElms.Exists(aSrc(nIdx)) Then ' found it 
      vRepElm = aSrc(nIdx) 
      ReDim aLocs(UBound(aLocs) + 2) 
      ' location of first occurrence 
      aLocs(UBound(aLocs) - 1) = dicElms(aSrc(nIdx)) 
      ' location of this occurrence 
      aLocs(UBound(aLocs) ) = nIdx 
     Else 
      ' location of first occurrence 
      dicElms(aSrc(nIdx)) = nIdx 
     End If 
     End If 
    Next 
    locRep = aLocs 
End Function 

Пробное:

------------------------------------------------- 
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 
Src: 1 3 6 4 7 6 9 2 6 6 6 6 8 
Res: 2 5 8 9 10 11 
ok 

Src: 
Res: 
ok 

Src: 1 2 3 
Res: 
ok 

Src: 1 1 2 3 4 5 6 
Res: 0 1 
ok 

Src: 1 2 3 4 5 6 6 
Res: 5 6 
ok 

================================================= 

Answer 5

using namespace std; 
list<int> find_duplicate_idx(const vector<int>& A) 
{ 
hash_map<int, int> X; 
list<int> idx; 
for (int i = 0; i < A.size(); ++ i) { 
    hash_map<int, int>::iterator it = X.find(A[i]); 
    if (it != X.end()) { 
    idx.push_back(it->second); 
    idx.push_back(i); 
    for (int j = i + 1; j < A.size(); ++j) 
     if (A[j] == A[i]) 
     idx.push_back(j); 
    return idx; 
    } 
    X[A[i]] = i; 
} 
return idx; 
} 

Это решение моего друга при условии. Спасибо SETI от mitbbs.com

Answer 6

В ситуации интервью, я думаю, ваш шанс задать вопрос, например, сколько цифр? какой диапазон чисел? вы можете указать, что оптимальный алгоритм может меняться в зависимости.

Это дает вам возможность показать, как вы решаете проблемы.

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

Answer 7

Используйте хэш-карту, чтобы решить:

private int getRepeatedElementIndex(int[] arr) { 

    Map<Integer, Integer> map = new HashMap(); 
    // find the duplicate element in an array 
    for (int i = 0; i < arr.length; i++) { 
     if(map.containsKey(arr[i])) { 
      return i; 
     } else { 
      map.put(arr[i], i); 
     } 
    } 
    throw new RuntimeException("No repeated element found"); 
} 

Временная сложность: O (п)

Space сложность: O (п)

эффективность