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

Question

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

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

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

Есть идеи для эффективных алгоритмов?

Answer 1

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

Answer 2

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

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

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

Answer 3

Используйте хеш-карту для ее решения:

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 (n)

Пространственная сложность: O (n)

Answer 4

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 5

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

1. все вязы списка должны быть просмотрены (=> цикл по списку)
2. до того, как повторный вяз станет известен, сохраните вяз=> location / index в хэше / словаре
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 6

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

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

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

Answer 7

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