Пронађите дупликате у датом низу када елементи нису ограничени на распон


Ниво тешкоће Лако
Често питани у адобе амазонка Фацтсет МАК УХГ Оптум
Ред Хасхинг

Проблем „Пронађи дупликате у датом низу када елементи нису ограничени на опсег“ наводи да имате поредак који се састоји од н интегерс. Проблем наводи да би се пронашли дуплицирани елементи ако су присутни у низу. Ако такав елемент не постоји, вратите -1.

Пример

Пронађите дупликате у датом низу када елементи нису ограничени на распон

[ 2, 4, 6, 2, 7, 8, 9, 7]
2, 7

Објашњење

У овом низу 2 и 7 су једини дуплицирани елементи.

[134, 567, 134, 456, 1000, 567, 7]
134, 567

Објашњење

У овом низу 134 и 567 су једини дуплицирани елементи.

Алгоритам за проналажење дупликата елемената у низу

  1. Изјави Мапа.
  2. Спремите елемент низа и његову фреквенцију на мапу.
  3. Изјавите Боолеан варијабла дупликат да провери да ли дуплирани елемент постоји или не.
  4. Пређите преко мапе и проверите који елемент има фреквенцију већу од 1.
  5. Ако је фреквенција већа од 1, одштампајте елемент и иницијализујте дупликат на труе.
  6. Проверите да ли је дупликат нетачан ако услов задовољава, а затим испишите -1.

Објашњење

Задали смо проблем у којем морамо одредити дупликате елемената у низу и исписати те елементе. За ово ћемо користити а ХасхМап за чување фреквенција сваког елемента низа. Фреквенције, које су веће од 1, значе да се број понавља у низу. То значи двострукост тог броја.

Прошли смо два аргумента као низ и његова дужина. Сада прогласите још једну променљиву која ће бити логичка променљива иницијализована као лажна. Затим га касније проверите ако тада не нађемо дуплицирани елемент дупликат остаје лажно, биће истина. Затим помоћу ове мапе откријте да је елемент који има фреквенцију већу од 1, штампаћемо те елементе. И тако проналазимо дупликате елемената у низу.

Размотримо пример:

арр [] = {2,4,6,3,1,2,4,7};

и = 0, арр [и] = 2; фрек = {2: 1}

i=1, arr[i]=4; freq={2:1,4:1}

i=2, arr[i]=6; freq={2:1,4:1,6:1}

i=3, arr[i]=3; freq={2:1,4:1,6:1,3:1}

i=4, arr[i]=1; freq={2:1,4:1,6:1,3:1,1:1}

и = 5, арр [и] = 2; фрек = {2: 2,4: 1,6: 1,3: 1,1: 1} // повећање учесталости '2' са 1 на 2,

и = 6, арр [и] = 4; фрек = {2: 2,4: 2,6: 1,3: 1,1: 1} // повећање учесталости '4' са 1 на 2,

i=7, arr[i]=7; freq={2:2,4:2,6:1,3:1,1:1,7:1}

на мапи имамо фрекв: {2: 2,4: 2,6: 1,3: 1,1: 1,7: 1}

Сада пређите преко мапе и сазнајте која вредност има фреквенцију већу од 1. Већ смо овде покренули логичку варијаблу дупликат као нетачну, па ћемо, када проверимо која је фреквенција већа од 1, ажурирати дупликат као истинит. А ако изађемо из петље са дупликатом као фалсе, значи да елемент дупликата не постоји у низу.

Јасно је да 2 и 4 имају фреквенцију већу од оне која значи да су дуплицирани елементи.

И наш излаз постаје [2 4]. Дакле, ово је био пример како у низу проналазимо дупликате елемената.

код

Ц ++ код за проналажење дупликата елемената у низу

#include <iostream>
#include <unordered_map>

using namespace std;

void getDuplicate(int arr[], int n)
{
    unordered_map<int,int> freq;

    for(int index=0;index<n;index++)
        freq[arr[index]]++;

    bool duplicate=false;
    unordered_map<int,int> :: iterator itr;
    for(itr=freq.begin();itr!=freq.end();itr++)
    {
        if(itr->second > 1)
        {
            cout<<itr->first<<" ";
            duplicate=true;
        }
    }
    if(!duplicate)
        cout<<"-1"<<endl;
}
int main()
{
    int arr[]={2,4,6,3,1,2,4,7};
    int n=sizeof(arr)/sizeof(arr[0]);
    getDuplicate(arr,n);
    return 0;
}
4 2

Јава код за проналажење дупликата елемената у низу

import java.util.HashMap;
class findDuplicateNumber
{
    public static void getDuplicate(int arr[], int n)
    {
        HashMap<Integer, Integer> freq=new HashMap<Integer, Integer>();
        for(int i=0; i<n; i++)
        {
            if(freq.containsKey(arr[i]))
            {
                freq.put(arr[i],freq.get(arr[i])+1);
            }
            else
            {
                freq.put(arr[i],1);
            }
        }
        boolean duplicate=false;
        for(int i:freq.keySet())
        {
            if(freq.get(i)> 1)
            {
                System.out.print(i+" ");
                duplicate=true;
            }
        }
        if(!duplicate)
            System.out.println("-1");
    }
    public static void main(String [] args)
    {
        int arr[]= {2,4,6,3,1,2,4,7};
        int len=arr.length;
        getDuplicate(arr,len);
    }
}
2 4

Анализа сложености

Сложеност времена

Он) где „Н“ је број елемената у низу. Стога проблем „Пронађи дупликате у датом низу када елементи нису ограничени на опсег“ има линеарну временску сложеност.

Сложеност простора

Он) где „Н“ је број елемената у низу. Сложеност свемира је такође линеарна, јер у најгорем случају можемо имати све различите елементе.