Как найти повторяющиеся цифры в массиве

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

Один из способов решения этой задачи – использовать словарь. Можно создать словарь, в котором каждому элементу списка соответствует количество его повторений, и в цикле перебрать элементы списка, добавляя их в словарь.

Вот пример такой функции:

def count_repeats(lst):
    """
    Возвращает словарь, в котором каждому элементу списка lst соответствует
    количество его повторений.
    """
    repeats = {}
    for item in lst:
        if item in repeats:
            repeats[item] += 1
        else:
            repeats[item] = 1
    return repeats



# Пример использования функции
lst = [10, 10, 23, 10, 123, 66, 78, 123]
repeats = count_repeats(lst)
print(repeats)  # {10: 3, 123: 2}

Функция count_repeats принимает на вход список lst, перебирает его элементы и добавляет их в словарь repeats. Если элемент уже есть в словаре, то увеличивается значение соответствующей пары ключ-значение, если же элемента еще нет в словаре, то добавляется пара с ключом равным этому элементу и значением 1.

Вы можете использовать эту функцию, чтобы найти повторяющиеся элементы в списке и количество их повторений.

Вы также можете использовать функцию Counter из модуля collections, чтобы посчитать количество повторений элементов списка. Эта функция возвращает словарь, в котором каждому элементу списка соответствует количество его повторений.

Вот пример кода, который использует функцию Counter:

from collections import Counter

def count_repeats(lst):
    """
    Возвращает словарь, в котором каждому элементу списка lst соответствует
    количество его повторений.
    """
    return Counter(lst)


# Пример использования функции
lst = [10, 10, 23, 10, 123, 66, 78, 123]
repeats = count_repeats(lst)
print(repeats)  # Counter({10: 3, 123: 2})

В этом коде сначала импортируется модуль collections и функция Counter, а затем определяется функция count_repeats, которая принимает список lst и возвращает результат вызова функции Counter на этом списке.

Вы также можете использовать функцию most_common из модуля collections, чтобы найти топ-N самых часто встречающихся элементов в списке. Эта функция принимает список и число N, и возвращает список кортежей, каждый из которых содержит элемент и количество его повторений.

Вот пример кода, который использует функцию most_common:

from collections import Counter

def find_top_repeats(lst, n):
    """
    Возвращает топ-N самых часто встречающихся элементов в списке lst.
    """
    return Counter(lst).most_common(n)


# Пример использования функции
lst = [10, 10, 23, 10, 123, 66, 78, 123]
top_repeats = find_top_repeats(lst, 2)
print(top_repeats)  # [(10, 3), (123, 2)]

В этом коде сначала импортируется модуль collections и функция Counter, а затем определяется функция find_top_repeats, которая принимает список lst и число n, и возвращает результат вызова функции most_common

Если вам нужно найти только уникальные элементы в списке, то можете использовать функцию set. Эта функция создает множество из элементов списка, удаляя повторяющиеся элементы. Множество не содержит повторяющихся элементов, поэтому вы можете использовать его, чтобы найти уникальные элементы в списке.

Вот пример кода, который использует функцию set:

def find_unique(lst):
    """
    Возвращает список уникальных элементов в списке lst.
    """
    return list(set(lst))


# Пример использования функции
lst = [10, 10, 23, 10, 123, 66, 78, 123]
unique = find_unique(lst)
print(unique)  # [66, 78, 10, 123, 23]

В этом коде определяется функция find_unique, которая принимает список lst и возвращает список уникальных элементов. Для этого список преобразуется в множество

Если вам нужно найти только уникальные элементы в списке и посчитать их количество, то можете соединить два предыдущих подхода: сначала использовать функцию set для нахождения уникальных элементов, а затем функцию count_repeats для подсчета их количества.

Вот пример кода, который реализует этот подход:

def count_unique(lst):
    """
    Возвращает словарь, в котором каждому уникальному элементу списка lst соответствует
    количество его повторений.
    """
    repeats = {}
    for item in set(lst):
        repeats[item] = lst.count(item)
    return repeats


# Пример использования функции
lst = [10, 10, 23, 10, 123, 66, 78, 123]
unique_counts = count_unique(lst)
print(unique_counts)  # {66: 1, 78: 1, 10: 3, 123: 2}

В этом коде определяется функция count_unique, которая принимает список lst и возвращает словарь, в котором каждому уникальному элементу списка

Ввод: 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-разработчик
Узнать больше

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

Например,

Потренируйтесь в этой проблеме

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

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

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

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

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

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

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

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

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

Подход 3: Использование исключающего ИЛИ

Мы также можем решить эту проблему, взяв xor всех элементов массива с номерами 1 в n-1. Поскольку одни и те же элементы будут компенсировать друг друга, как a^a = 0, 0^0 = 0 а также a^0 = a, у нас останется повторяющийся элемент. Этот подход демонстрируется ниже на C, Java и Python:

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

Подход 4: использование разницы в сумме

Наконец, пост будет неполным без этого хрестоматийного решения: найти сумму всех элементов и найти разницу между ними и всеми элементами, которые там должны быть. Это показано ниже на C++, Java и Python:

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