Знайсці дублікаты ў дадзеным масіве, калі элементы не абмежаваныя дыяпазонам


Узровень складанасці Лёгка
Часта пытаюцца ў Саман амазонка Факты MAQ UHG Optum
масіў хэшавання

У праблеме "Знайсці дублікаты ў дадзеным масіве, калі элементы не абмежаваныя дыяпазонам" гаворыцца, што ў вас ёсць масіў які складаецца з чаго-н цэлыя. Пастаноўка праблемы заключаецца ў высвятленні дублікатаў элементаў, калі яны ёсць у масіве. Калі такога элемента няма, вярніце -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. Абвясціце Boolean пераменная дубляваць каб праверыць, ці існуе дублікат элемента.
  4. Перагляньце карту і праверце, які элемент мае частату большую за 1.
  5. Калі частата перавышае 1, раздрукуйце элемент і ініцыялізуйце дублікат у true.
  6. Праверце, ці паўтараецца дублікат, калі ўмова задавальняе, надрукуйце -1.

Тлумачэнне

Мы паставілі задачу, пры якой мы павінны вызначыць дублікаты элементаў у масіве і надрукаваць гэтыя элементы. Для гэтага мы будзем выкарыстоўваць a HashMap для захоўвання частот кожнага элемента масіва. Частаты, якія перавышаюць 1, азначаюць, што лік паўтараецца ў масіве. Гэта азначае дубліраванне гэтага ліку.

Мы перадалі два аргументы як масіў і яго даўжыню. Цяпер абвясціце яшчэ адну зменную, якая будзе лагічнай зменнай, ініцыялізаванай як ілжывая. Тады пазней праверце, калі мы не знойдзем дублікатаў дубляваць застаецца ілжывым, інакш гэта будзе праўдай. Затым, выкарыстоўваючы гэтую карту, даведайцеся, які элемент мае частату больш за 1, мы будзем раздрукоўваць гэтыя элементы. І вось як мы знаходзім дублікаты элементаў у масіве.

Давайце разгледзім прыклад:

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

i = 0, arr [i] = 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}

i = 5, arr [i] = 2; freq = {2: 2,4: 1,6: 1,3: 1,1: 1} // павялічваючы частату "2" з 1 да 2,

i = 6, arr [i] = 4; freq = {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]. Такім чынам, гэта быў прыклад таго, як мы знаходзім дублікаты элементаў у масіве.

код

Код C ++ для пошуку дублікатаў элементаў у масіве

#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

Код Java для пошуку дублікатаў элементаў у масіве

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

Аналіз складанасці

Складанасць часу

Аб (п) дзе "П" - колькасць элементаў у масіве. Такім чынам, задача "Знайсці дублікаты ў дадзеным масіве, калі элементы не абмежаваныя дыяпазонам" мае лінейную часавую складанасць.

Касмічная складанасць

Аб (п) дзе "П" - колькасць элементаў у масіве. Касмічная складанасць таксама лінейная, бо ў горшым выпадку ў нас могуць быць усе розныя элементы.