Найти дубликат в массиве целых чисел

Ответ 1

• Возьмите последний элемент (x).

• Сохраните элемент в позиции x (y).

• Если x == y, вы нашли дубликат.

• Запишите положение x с помощью x.

• Назначьте x = y и продолжайте с шага 2.

Вы в основном сортируете массив, это возможно, потому что вы знаете, где элемент должен быть вставлен. O (1) дополнительное пространство и сложность времени O (n). Вам просто нужно быть осторожным с индексами, для простоты я предположил, что первый индекс здесь 1 (не 0), поэтому нам не нужно делать +1 или -1.

Изменить: без изменения входного массива

Этот алгоритм основан на идее, что мы должны найти точку входа цикла перестановки, затем мы также нашли дубликат (опять-таки 1-основанный массив для простоты):

Пример:

2 3 4 1 5 4 6 7 8

Запись: 8 7 6

Цикл перестановки: 4 1 2 3

Как мы видим, дубликат (4) является первым числом цикла.

• Поиск цикла перестановок

  • x = последний элемент
  • x = элемент в позиции x
  • повторите шаг 2. n раз (всего), это гарантирует, что мы ввели цикл

• Измерение длины цикла

  • a = последний x сверху, b = последний x сверху, счетчик c = 0
  • a = элемент в позиции a, b = elment в позиции b, b = элемент в позиции b, С++ (поэтому мы делаем 2 шага вперед с b и 1 шаг вперед в цикле с a)
  • если a == b длина цикла c, в противном случае продолжить с шага 2.

• Поиск точки входа в цикл

  • x = последний элемент
  • x = элемент в позиции x
  • повторите шаг 2. c раз (всего)
  • y = последний элемент
  • если x == y, то x является решением (x сделал один полный цикл, а y вот-вот вступит в цикл)
  • x = элемент в позиции x, y = элемент в позиции y
  • повторите шаги 5 и 6. до тех пор, пока не будет найдено решение.

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

Пример сверху:

• x принимает следующие значения: 8 7 6 4 1 2 3 4 1 2

• a принимает следующие значения: 2 3 4 1 2
  b принимает следующие значения: 2 4 2 4 2
  поэтому c = 4 (да, есть 5 чисел, но c только увеличивается при выполнении шагов, а не изначально)

• x принимает следующие значения: 8 7 6 4 | 1 2 3 4
  y принимает следующие значения: | 8 7 6 4
  x == y == 4 в конце, и это решение!

Пример 2, указанный в комментариях: 3 1 4 6 1 2 5

• Цикл ввода: 5 1 3 4 6 2 1 3

• Длина измерительного цикла:
  a: 3 4 6 2 1 3
  b: 3 6 1 4 2 3
  c = 5

• Поиск точки входа:
  x: 5 1 3 4 6 | 2 1
  y: | 5 1
  x == y == 1 - это решение

Ответ 2

Вот возможная реализация:

function checkDuplicate(arr) {
  console.log(arr.join(", "));
  let  len = arr.length
      ,pos = 0
      ,done = 0
      ,cur = arr[0]
      ;
  while (done < len) {
    if (pos === cur) {
      cur = arr[++pos];
    } else {
      pos = cur;
      if (arr[pos] === cur) {
        console.log(`> duplicate is ${cur}`);
        return cur;
      }
      cur = arr[pos];
    }
    done++;
  }
  console.log("> no duplicate");
  return -1;
}

for (t of [
     [0, 1, 2, 3]
    ,[0, 1, 2, 1]
    ,[1, 0, 2, 3]
    ,[1, 1, 0, 2, 4]
  ]) checkDuplicate(t);

Ответ 3

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

Примечание. Предположим, что вектор индексируется начиная с 1. Так как он, вероятно, индексируется начиная с 0 (на большинстве языков), вы можете реализовать "элемент флага в индексе i" с помощью "Отменить элемент в индекс i-1".

• Установите я в 0 и выполните следующий цикл:
  • Приращение я до тех пор, пока элемент я не будет заблокирован.
  • Установите j в я и выполните следующий цикл:
    • Установите j в вектор [j].
    • если элемент в j помечен, j является дубликатом. Завершите оба цикла.
    • Отметьте элемент в j.
    • Если j!= i, продолжайте внутренний цикл.
• Переместите вектор, устанавливая каждый элемент в его абсолютное значение (т.е. отмените все, чтобы восстановить вектор).

Ответ 4

• Это зависит от того, какие инструменты вы можете использовать (приложение). В настоящее время существует множество инфраструктур/библиотек. Для exmaple в случае стандартного С++ вы можете использовать std:: map < > , как упоминалось в maraca.

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

двоичное дерево expl. ссылка: https://www.wikiwand.com/en/Binary_tree