მოცემულ მასივში იპოვნეთ ეგზემპლარები, როდესაც ელემენტები არ შემოიფარგლება დიაპაზონით


Რთული ტური Easy
ხშირად ეკითხებიან Adobe Amazon ფაქტები MAQ UHG Optum
Array ჰაშინგი

პრობლემა "იპოვნეთ ეგზემპლარი მოცემულ მასივში, როდესაც ელემენტები არ შემოიფარგლება დიაპაზონში" აღნიშნავს, რომ თქვენ გაქვთ მასივი შედგება ნ რიცხვები. პრობლემა აცხადებს მას მასივში არსებული დუბლირებული ელემენტების გასარკვევად. თუ ასეთი ელემენტი არ არსებობს, დააბრუნე -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.

განმარტება

ჩვენ მივეცით პრობლემა, რომელშიც უნდა განვსაზღვროთ მასივის დუბლირებული ელემენტები და დავბეჭდოთ ისინი. ამისათვის ჩვენ ვაპირებთ გამოვიყენოთ ა HashMap თითოეული მასივის ელემენტის სიხშირეების შესანახად. სიხშირეები, რომლებიც 1-ზე მეტია, ნიშნავს, რომ რიცხვი იმეორებს მასივს. ეს ნიშნავს ამ რიცხვის დუბლიკატს.

მასივი და მისი სიგრძე გადავიტანეთ ორი არგუმენტი. ახლა გამოაცხადეთ კიდევ ერთი ცვლადი, რომელიც იქნება ლოგიკური ცვლადის ინიცირებული ცრუ. შემდეგ მოგვიანებით შეამოწმეთ იგი, თუ შემდეგ ვერ იპოვით რაიმე დუბლიკატ ელემენტს დუბლიკატი ყალბი რჩება სხვა შემთხვევაში ეს სიმართლე იქნება. შემდეგ ამ რუკის საშუალებით გაირკვეს, თუ რომელი ელემენტია სიხშირე 1-ზე მეტი, ჩვენ ამ ელემენტებს ბეჭდავთ. და ასე ვხვდებით მასივის დუბლიკატ ელემენტებს.

განვიხილოთ მაგალითი:

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

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

ჩვენ გვაქვს Freq რუკაზე: {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

სირთულის ანალიზი

დროის სირთულე

O (n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა. ამრიგად, "იპოვნეთ ეგზემპლარი მოცემულ მასივში, როდესაც ელემენტები არ შემოიფარგლება დიაპაზონით" პრობლემას აქვს ხაზოვანი დროის სირთულე.

სივრცის სირთულე

O (n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა. სივრცის სირთულე ასევე ხაზოვანია, რადგან უარეს შემთხვევაში შეიძლება გვქონდეს ყველა განსხვავებული ელემენტი.