Учитывая массив целых чисел, найдите первый повторяющийся элемент в нем. Нам нужно найти элемент, который встречается более одного раза и чей индекс первого появления наименьший.
Примеры:
Input: arr[] = {10, 5, 3, 4, 3, 5, 6} Output: 5 [5 is the first element that repeats] Input: arr[] = {6, 10, 5, 4, 9, 120, 4, 6, 10} Output: 6 [6 is the first element that repeats]
Простое решение заключается в использовании двух вложенных циклов. Внешний цикл выбирает элемент один за другим, внутренний цикл проверяет, повторяется ли элемент или нет. Как только мы находим элемент, который повторяется, мы разбиваем циклы и печатаем элемент. Сложность времени этого решения O (n 2 )
Мы можем использовать сортировку, чтобы решить проблему за O (nLogn) время. Ниже приведены подробные шаги.
1) Скопировать данный массив во вспомогательный массив temp [].
2) Сортировка временного массива с использованием алгоритма временной сортировки O (nLogn).
3) Сканирование входного массива слева направо. Для каждого элемента подсчитайте его вхождения в temp [], используя бинарный поиск . Как только мы находим элемент, который встречается более одного раза, мы возвращаем элемент. Этот шаг может быть выполнен за O (nLogn) время.
Мы можем использовать хеширование, чтобы решить это в среднем за O (n) раз. Идея состоит в том, чтобы обойти заданный массив справа налево и обновить минимальный индекс всякий раз, когда мы находим элемент, который был посещен справа. Спасибо Мохаммаду Шахиду за предложенное решение.
Ниже приводится реализация этой идеи.
|
Джава
|
python3
|
C #
|
Выход:
The first repeating element is 5
Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.
Рекомендуемые посты:
- Найти единственный повторяющийся элемент в отсортированном массиве размером n
- Найти последний элемент после удаления каждого второго элемента в массиве из n целых чисел
- По заданному массиву и двум целым числам l и r найдите k-й по величине элемент в диапазоне [l, r]
- k-й отдельный (или неповторяющийся) элемент в массиве.
- Найти два неповторяющихся элемента в массиве повторяющихся элементов
- Найти два повторяющихся элемента в данном массиве
- Найти сумму неповторяющихся (различных) элементов в массиве
- Найти любой из нескольких повторяющихся элементов в массиве только для чтения
- Найти пару с максимальным произведением в массиве целых чисел
- Неповторяющийся элемент
- Найти целые числа, которые делят максимальное количество элементов массива
- Найти элемент в массиве так, чтобы сумма левого массива была равна сумме правого массива
- Минимальное произведение k целых чисел в массиве положительных целых чисел
- Найти элемент в массиве, который разделяет все элементы массива
- Найти, если массив имеет элемент, значение которого составляет половину суммы массива
0.00 (0%) 0 votes