Рубрики

Найти дубликаты в данном массиве, когда элементы не ограничены диапазоном

Дан массив из n целых чисел. Задача — распечатать дубликаты в заданном массиве. Если дубликатов нет, выведите -1.

Примеры:

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

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

Примечание: дубликаты элементов могут быть напечатаны в любом порядке.

Простой подход : с помощью двух циклов. Он имеет временную сложность O (n 2 ).

Эффективный подход : используйте unordered_map для хеширования. Подсчитать частоту встречаемости каждого элемента и печатать элементы с частотой более 1. unordered_map используется, поскольку диапазон целых чисел неизвестен. Для Python используйте словарь, чтобы сохранить число в качестве ключа и его частоту в качестве значения. Словарь может быть использован, так как диапазон целых чисел не известен.

C ++

// C ++ программа для поиска
// дублирует в указанном массиве
#include <bits/stdc++.h>

using namespace std;

  
// функция поиска и печати дубликатов

void printDuplicates(int arr[], int n)

{

    // unordered_map для хранения частот

    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++)

    {

        // если частота больше 1

        // распечатать элемент

        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())

        {

            // если частота больше 1

            // распечатать элемент

            if(entry.getValue() > 1){

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

                dup = true;

            }

        }

        // дубликатов нет

        if(!dup){

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

        }

    }

}

python3

# Код Python 3 для поиска дубликатов
# используя словарный подход.

def printDuplicates(arr):

    dict = {}

  

    for ele in arr:

        try:

            dict[ele] += 1

        except:

            dict[ele] = 1

              

    for item in dict:

          

         # если частота больше 1

         # распечатать элемент

        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 #

// 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)

        {

            // если частота больше 1

            // распечатать элемент

            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);

    }

}

  
// Этот код предоставлен
// sanjeev2552


Выход:

12 11 5

Сложность времени: O (n)

Похожие сообщения:
Распечатать все отдельные элементы заданного целочисленного массива
Найти дубликаты за O (n) времени и O (1) лишних пробелов | Комплект 1
Дублирует массив в O (n) и использует O (1) лишний пробел | Set-2
Распечатать все дубликаты во входной строке

Эта статья предоставлена Аюшем Джаухари . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Найти дубликаты в данном массиве, когда элементы не ограничены диапазоном

0.00 (0%) 0 votes