Verilmiş massivdə ilk təkrar ədədi tapın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg Citadel eBay Facebook Goldman Sachs google Intuit microsoft Nutanix Kahin PayPal Salesforce Arzu Yahoo
Geyim Sükut Axtarış ZyngaBaxılıb 221

Problem bəyanat

An-da birdən çox təkrarlanan rəqəm ola bilər array ancaq müəyyən bir sıra içərisində ilk təkrarlanan sayını tapmaq lazımdır (ikinci dəfə baş verir).

misal

Input

12

5 4 2 8 9 7 12 5 6 12 4 7

Buraxılış

5 ilk təkrarlanan elementdir

İlk təkrar nömrəni tapmaq üçün yanaşma 1

Sadəcə, sıra elementlərinin dəyərlərini qarışdırdığımız və meydana gəlmə sayını artırdığımız yerdə Hashing istifadə edə bilərik. 1 saylı yəni əvvəldən meydana gələn bir element əldə edən kimi ilk təkrar elementi alırıq.

Alqoritm

1. Massivin hər bir elementini keçin.

2. Hər bir elementin tezliyini artırın.

3. Tezliyi 1-dən çox olan hər hansı bir element varsa, bu nömrəni birbaşa çap edin.

Həyata keçirilməsi

C ++ Proqramı

Java Proqramı

import java.util.HashMap;
import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        HashMap <Integer,Integer> m = new HashMap<Integer, Integer>();
        int ans=0;
        for(int i=0;i<n;i++)
        {
            int x = m.get(a[i])==null ? 1: m.get(a[i])+1;
            m.put(a[i], x);
            if(m.get(a[i])>1)
            {
                ans=a[i];
                break;
            }
        }
        if(ans==0)
        {
            System.out.println("No element repeated");
        }
        else
        {
          System.out.println(ans);
        }
    }
}
12
5 4 2 8 9 7 12 5 6 12 4 7
5

İlk təkrar nömrəni tapmaq üçün mürəkkəblik analizi

Zaman Mürəkkəbliyi - O (N) burada N massivin ölçüsüdür. Burada sıra üzərində təkrarlanır və elementlərin tezliyini / sayını hash map-də saxlayırıq.

Kosmik Mürəkkəblik - O (N) çünki o tezlik elementini sayırıq və hash xəritəsi mümkün olan maksimum ölçüsü O (n) -dir.

İlk təkrar nömrəni tapmaq üçün 2 yanaşması

Burada həmin elementi massivdə saxlayan və ya saxlamayan xəritədən istifadə edirik. Element mövcuddursa, ehtiva edir doğru xəritədəki elementə münasibətdə. Element mövcud deyilsə, onu saxlayır saxta xəritədəki elementə münasibətdə.

Alqoritm

1. Dizini elementinin dəyərini açar halına gətirərək Xəritədən istifadə edin və açar dəyər cütü kimi sayın.

2. Bir cütü 1 kimi sayaraq başlayın və artırın.

3. Sayı 1 olan bir element əldə edən kimi ilk təkrar elementi alırıq

Həyata keçirilməsi

C ++ Proqramı

#include <bits/stdc++.h>
using namespace std;
int main()
{
  
  int n;
  cin>>n;
  int arr[n];
  for(int i=0;i<n;i++)
  {
      cin>>arr[i];
  }
  map <int,bool> M; // create a map with key as the array element and value as if it is present or not
  map <int,bool> :: iterator it;
  for(int i=0;i<n;i++)
    {
      it = M.find(arr[i]); //find the array element in map
      if(it != M.end()) // if present then it is the first element to be repeated
        {
          cout<<arr[i] <<endl;
          return 0;
        }
      else
        M.insert(make_pair(arr[i],true)); //else insert it into the map setting the value as true
    }
  cout<<"No element repeated"<<endl;
  return 0;
  
}

Java Proqramı

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        Map <Integer,Integer> m = new HashMap<Integer, Integer>() {}; // create a map with key as the array element and value as if it is present or not
        int frank=0;
        for(int i=0;i<n;i++)
        {
            boolean temp = m.containsValue(a[i]);
            if(temp) // if present then it is the first element to be repeated
            {
                System.out.println(a[i]);
                frank=1;
                i=n;
            }
            else
            {
               m.put(a[i],1); //else insert it into the map setting the value as true
            }
          }
        if(frank==0)
        System.out.println("No element repeated");
    }
}
6
1 2 3 4 5 6
No element repeated

İlk təkrar nömrəni tapmaq üçün mürəkkəblik analizi

Zaman Mürəkkəbliyi - O (NlogN) çünki xəritəyə daxil olmaq O (logn) vaxt aparır və burada xəritəyə n element daxil edirik.

Kosmik Mürəkkəblik - O (N) çünki bu elementin mövcud olmadığını göstərən bir xəritədən istifadə edirik.

References

Translate »