Как найти повторяющиеся элементы в массиве c

То есть для вывода результирующего массива вам также нужно использовать цикл, естественно, правильно указав диапазон допустимых индексов.

Поиск одинаковых элементов массива

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

Поиск в массиве одинаковых элементов
Необходимо найти в массиве одинаковые элементы и вывести значение одного из элементов. Если в.

Поиск количества одинаковых букв массива
Сделал код с помощью которого можно зеркально отразить введенное слово. Надо подсчитать количество.

Поиск одинаковых элементов в двумерном массиве
Помогите написать программу на поиск одинаковых элементов двумерного массива

Найдите повторяющийся элемент в массиве с ограниченным диапазоном

Учитывая ограниченный диапазон размеров массива n содержащие элементы от 1 до n-1 с повторяющимся элементом найдите в нем повторяющийся номер, не используя лишнего пробела.

Input: < 1, 2, 3, 4, 4 >
Output: The duplicate element is 4

Input: < 1, 2, 3, 4, 2 >
Output: The duplicate element is 2

Подход 1: Использование хеширования

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

Ниже приведена реализация на C++, Java и Python, основанная на приведенной выше идее:

C++

using namespace std ;
// Функция для поиска повторяющегося элемента в массиве с ограниченным диапазоном
int findDuplicate ( vector < int >const &nums )
int n = nums . size ( ) ;
// создаем посещаемый массив размером `n+1`
// мы также можем использовать карту вместо посещаемого массива
vector < bool >visited ( n + 1 ) ;
// помечаем каждый элемент массива как посещенный и
// возвращаем его, если видели раньше
for ( int i : nums )
// если элемент был замечен раньше
if ( visited [ i ] ) < // отметить элемент как посещенный visited [ i ] = true ; // дубликат не найден // входной массив содержит `n` чисел от 1 до `n-1` с одним дубликатом vector < int >nums = < 1 , 2 , 3 , 4 , 4 >;
cout << "The duplicate element is " << findDuplicate ( nums ) ;

результат:

The duplicate element is 4

Java

class Main
// Функция для поиска повторяющегося элемента в массиве с ограниченным диапазоном
public static int findDuplicate ( int [ ] nums )
// создаем посещаемый массив размером `n+1`
// мы также можем использовать карту вместо посещаемого массива
boolean visited [ ] = new boolean [ nums . length + 1 ] ;
// помечаем каждый элемент массива как посещенный и
// возвращаем его, если видели раньше
for ( int value : nums )
// если элемент был замечен раньше
if ( visited [ value ] ) < return value ; // отметить элемент как посещенный visited [ value ] = true ; // дубликат не найден public static void main ( String [ ] args ) // входной массив содержит `n` чисел от 1 до `n-1` // с одним дубликатом, где `n` - длина массива int [ ] nums = < 1 , 2 , 3 , 4 , 4 >;
System . out . println ( "The duplicate element is " + findDuplicate ( nums ) ) ;

результат:

The duplicate element is 4

Python

# Функция поиска повторяющегося элемента в списке с ограниченным диапазоном
def findDuplicate ( nums ) :
# создает список посещений размером `n+1`
# мы также можем использовать словарь вместо списка посещенных
visited = [ False ] * ( len ( nums ) + 1 )
# для каждого элемента в списке, отметить его как посещенный и
# верните его, если видели раньше
for i in nums :
#, если элемент был замечен раньше
if visited [ i ] :
# пометить элемент как посещенный
visited [ i ] = True
# дубликат не найден
if __name__ == '__main__' :
# список ввода содержит `n` чисел от 1 до `n-1`
# с одним дубликатом, где `n = len(nums)`
nums = [ 1 , 2 , 3 , 4 , 4 ]
print ( 'The duplicate element is' , findDuplicate ( nums ) )

результат:

The duplicate element is 4

Временная сложность приведенного выше решения равна O(n) и требует O(n) дополнительное пространство, где n это размер ввода.

Подход 2: Использование индексов массива

Мы можем решить эту задачу в постоянном пространстве. Поскольку массив содержит все отдельные элементы, кроме одного, и все элементы лежат в диапазоне от 1 до n-1 , мы можем проверить наличие повторяющегося элемента, пометив элементы массива как отрицательные, используя индекс массива в качестве ключа. Для каждого элемента массива nums[i] , инвертировать знак элемента, присутствующего в индексе nums[i] . Наконец, еще раз пройдитесь по массиву, и если в индексе будет найдено положительное число i , то повторяющийся элемент i .

Приведенный выше подход требует двух обходов массива. Мы можем добиться того же только за один проход. Для каждого элемента массива nums[i] , инвертировать знак элемента, присутствующего в индексе nums[i] если он положительный; в противном случае, если элемент уже отрицательный, то это дубликат.

Алгоритм может быть реализован следующим образом на C++, Java и Python: