Как найти два одинаковых значения в массиве

Given an array of n integers. The task is to print the duplicates in the given array. If there are no duplicates then print -1. 

Examples: 

Input: {2, 10,10, 100, 2, 10, 11,2,11,2}
Output: 2 10 11

Input: {5, 40, 1, 40, 100000, 1, 5, 1}
Output: 5 40 1

Note: The duplicate elements can be printed in any order.

Simple Approach: The idea is to use nested loop and for each element check if the element is present in the array more than once or not. If present, then store it in a Hash-map. Otherwise, continue checking other elements.

Below is the implementation of the above approach:

Time Complexity: O(N²) 
Auxiliary Space: O(N)

Efficient Approach: Use unordered_map for hashing. Count frequency of occurrence of each element and the elements with frequency more than 1 is printed. unordered_map is used as range of integers is not known. For Python, Use Dictionary to store number as key and it’s frequency as value. Dictionary can be used as range of integers is not known.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

void printDuplicates(int arr[], int n)

{

    unordered_map<int, int> freq;

    for (int i=0; i<n; i++)

        freq[arr[i]]++;

    bool dup = false;

    unordered_map<int, int>:: iterator itr;

    for (itr=freq.begin(); itr!=freq.end(); itr++)

    {

        if (itr->second > 1)

        {

            cout << itr->first << " ";

            dup = true;

        }

    }

    if (dup == false)

        cout << "-1";

}

int main()

{

    int arr[] = {12, 11, 40, 12, 5, 6, 5, 12, 11};

    int n = sizeof(arr) / sizeof(arr[0]);

    printDuplicates(arr, n);

    return 0;

}

Java

import java.util.HashMap;

import java.util.Map;

import java.util.Map.Entry;

public class FindDuplicatedInArray

{

    public static void main(String[] args)

    {

        int arr[] = {12, 11, 40, 12, 5, 6, 5, 12, 11};

        int n = arr.length;

        printDuplicates(arr, n);

    }

    private static void printDuplicates(int[] arr, int n)

    {

        Map<Integer,Integer> map = new HashMap<>();

        int count = 0;

        boolean dup = false;

        for(int i = 0; i < n; i++){

            if(map.containsKey(arr[i])){

                count = map.get(arr[i]);

                map.put(arr[i], count + 1);

            }

            else{

                map.put(arr[i], 1);

            }

        }

        for(Entry<Integer,Integer> entry : map.entrySet())

        {

            if(entry.getValue() > 1){

                System.out.print(entry.getKey()+ " ");

                dup = true;

            }

        }

        if(!dup){

            System.out.println("-1");

        }

    }

}

Python3

def printDuplicates(arr):

    dict = {}

    for ele in arr:

        try:

            dict[ele] += 1

        except:

            dict[ele] = 1

    for item in dict:

        if(dict[item] > 1):

            print(item, end=" ")

    print("n")

if __name__ == "__main__":

    list = [12, 11, 40, 12,

            5, 6, 5, 12, 11]

    printDuplicates(list)

C#

using System;

using System.Collections.Generic;

class GFG

{

    static void printDuplicates(int[] arr, int n)

    {

        Dictionary<int,

                   int> map = new Dictionary<int,

                                             int>();

        int count = 0;

        bool dup = false;

        for (int i = 0; i < n; i++)

        {

            if (map.ContainsKey(arr[i]))

            {

                count = map[arr[i]];

                map[arr[i]]++;

            }

            else

                map.Add(arr[i], 1);

        }

        foreach (KeyValuePair<int,

                              int> entry in map)

        {

            if (entry.Value > 1)

                Console.Write(entry.Key + " ");

            dup = true;

        }

        if (!dup)

            Console.WriteLine("-1");

    }

    public static void Main(String[] args)

    {

        int[] arr = { 12, 11, 40, 12,

                     5, 6, 5, 12, 11 };

        int n = arr.Length;

        printDuplicates(arr, n);

    }

}

Javascript

<script>

function printDuplicates(arr, n)

{

    var freq = new Map();

    for(let i = 0; i < n; i++)

    {

        if (freq.has(arr[i]))

        {

            freq.set(arr[i], freq.get(arr[i]) + 1);

        }

        else

        {

            freq.set(arr[i], 1);

        }

    }

    var dup = false;

    for(let [key, value] of freq)

    {

        if (value > 1)

        {

            document.write(key + " ");

            dup = true;

        }

    }

    if (dup == false)

        document.write("-1");

}

var arr = [ 12, 11, 40, 12,

            5, 6, 5, 12, 11 ];

var n = arr.length;

printDuplicates(arr, n);

</script>

Time Complexity: O(N)
Auxiliary Space: O(N)   

Another Efficient Approach(Space optimization):            

• First we will sort the array for binary search function.
• we will find index at which arr[i] occur first time lower_bound 
• Then , we will find index at which arr[i] occur last time upper_bound            
• Then check if diff=(last_index-first_index+1)>1         
• If diff >1 means it occurs more than once and print                         

 Below is the implementation of the above approach:

Time Complexity: O(n*log₂n)
Auxiliary Space: O(1)

Related Post : 
Print All Distinct Elements of a given integer array 
Find duplicates in O(n) time and O(1) extra space | Set 1 
Duplicates in an array in O(n) and by using O(1) extra space | Set-2 
Print all the duplicates in the input string

This article is contributed by Ayush Jauhari. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Last Updated :
18 Apr, 2023

Like Article

Save Article

В этом посте мы обсудим, как найти все дубликаты в массиве в JavaScript.

1. Использование Array.prototype.indexOf() функция

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

В следующем примере кода показано, как реализовать это с помощью indexOf() метод:

Скачать  Выполнить код

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

Скачать  Выполнить код

2. Использование Set.prototype.has() функция

Кроме того, для повышения производительности вы можете использовать ES6. Установить структуру данных для эффективной фильтрации массива.

Следующее решение находит и возвращает дубликаты, используя has() метод. Это работает, потому что каждое значение в наборе должно быть уникальным.

Скачать  Выполнить код

Это все о поиске всех дубликатов в массиве в JavaScript.

Спасибо за чтение.

Пожалуйста, используйте наш онлайн-компилятор размещать код в комментариях, используя C, C++, Java, Python, JavaScript, C#, PHP и многие другие популярные языки программирования.

Как мы? Порекомендуйте нас своим друзьям и помогите нам расти. Удачного кодирования 🙂

Ввод: nums = [1,2,3,1]
Вывод: true

Ввод: nums = [1,2,3,4]
Вывод: false

Ввод: nums = [1,1,1,3,3,4,3,2,4,2]
Вывод: true

public boolean containsDuplicate(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int i : nums) {
        if (set.contains(i)) {
            return true;
        } else {
            set.add(i);
        }
    }
    return false;
}

Научитесь: Профессия Java-разработчик
Узнать больше

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

Задача

Итак, у нас есть массив. Это может быть массив любых объектов или примитивов. Для примера возьмём массив строк:

String[] animals = {"cat", "dog", "cow", "sheep", "cat", "dog"};

Теперь попробуем найти дублирующиеся строки в этом массиве.

Поиск дубликатов перебором

Сначала объявим вспомогательную коллекцию для хранения дубликатов – HashSet:

Set<T> duplicates = new HashSet<>();

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

Далее мы будем проходить по элементам массива, используя два цикла. В первом цикле мы извлекаем элемент массива и поочерёдно сравниваем его с остальными элементами массива, используя второй цикл:

for (int i = 0; i < a.length; i++) {
    T e1 = a[i];
    if (e1 == null) continue; // игнорируем null

    // сравниваем каждый элемент со всеми остальными
    for (int j = 0; j < a.length; j++) {
        if (i == j) continue; // не проверяем элемент с собой же
        T e2 = a[j];
        if (e1.equals(e2)) {
            // дубликат найден, сохраним его
            duplicates.add(e2);
        }
    }
}

И в конце возвратим найденные дубликаты:

return new ArrayList<>(duplicates);

Проверка

Проверим нашу программу:

String[] animals = {"cat", "dog", "cow", "sheep", "cat", "dog"};

System.out.println("Входной массив: " + Arrays.toString(animals));
System.out.println("Дубликаты: " + getDuplicatesWithIteration(animals));

Исходный код

package ru.javalessons.arrays;

import java.util.*;

public class ArrayFindDuplicates {
    public static void main(String[] args) {
        String[] animals = {"cat", "dog", "cow", "sheep", "cat", "dog"};

        System.out.println("Входной массив: " + Arrays.toString(animals));
        System.out.println("Дубликаты: " + getDuplicatesWithIteration(animals));
    }

    public static <T> List<T> getDuplicatesWithIteration(T[] a) {
        Set<T> duplicates = new HashSet<>();
        for (int i = 0; i < a.length; i++) {
            T e1 = a[i];
            if (e1 == null) continue; // игнорируем null

            // сравниваем каждый элемент со всеми остальными
            for (int j = 0; j < a.length; j++) {
                if (i == j) continue; // не проверяем элемент с собой же
                T e2 = a[j];
                if (e1.equals(e2)) {
                    // дубликат найден, сохраним его
                    duplicates.add(e2);
                }
            }
        }
        return new ArrayList<>(duplicates);
    }
}

Заключение

На данном примере мы разобрали, как находить дубликаты в массиве. Это может быть массив любых объектов.