Найдите повторяющийся элемент в массиве размера N, состоящем из первых M натуральных чисел.

Опубликовано: 22 Сентября, 2022

Дан массив arr[] размера N , содержащий перестановку чисел от 1 до M , а также элемент, который повторяется (один или несколько раз), задача состоит в том, чтобы найти повторяющийся элемент.

Примеры:

Input: arr[]={2, 6, 4, 3, 1, 5, 2}, N=7
Output:
2
Explanation: In arr[], all elements from 0 to 6 occurs once, except 2 which is repeated once.

Input: arr[]={2, 1, 3, 1, 1, 1}, N=6
Output:
1

Наивный подход . Наивным подходом было бы отсортировать массив и проверить наличие равных соседних элементов.

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

Подход: выполните следующие шаги, чтобы решить проблему:

  1. Инициализируйте две переменные M и sum для хранения максимального элемента и суммы массива соответственно.
  2. Перейдите массив arr и сделайте следующее:
    1. Добавить текущий элемент в сумму
    2. Сравните текущий элемент с M , чтобы вычислить максимальный элемент.
  3. Сохраните сумму перестановок от 1 до M в переменной, скажем, sum1 , используя формулу:
Sum of elements from 1 to X= X*(X+1)/2
  1. Вычислите ответ как разницу между суммой и суммой1 , деленную на количество дополнительных символов, т.е. (сумма-сумма1)/(NM) .

Ниже приведена реализация вышеуказанного подхода:


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

РЕКОМЕНДУЕМЫЕ СТАТЬИ