პირველი არა განმეორებადი ელემენტი


Რთული ტური Easy
ხშირად ეკითხებიან ბელზაბარი კომლი მედია MetLife Snapdeal სპრინკლერი ვუკერი
Array Hash Searching

მოცემულია მასივი A. მასივში უნდა ვიპოვოთ პირველი განმეორებითი ელემენტი.

მაგალითი

შეყვანის:

A [] = {2,1,2,1,3,4}

გამოყვანის:

პირველი განმეორებითი ელემენტია: 3

იმიტომ, რომ 1, 2 არ არის პასუხი, რადგან ისინი იმეორებენ და 4 არ არის პასუხი, რადგან ჩვენ უნდა ვიპოვნოთ პირველი განმეორებითი ელემენტი, რომელიც არის 3 და არა 4.

მიდგომა 1: უხეში ძალა

Მთავარი იდეა

ყველა ელემენტისთვის მასივი, ჩვენ ვიმეორებთ მთელ მასივს და თუ ეს ელემენტი არ განმეორდება, ჩვენ უბრალოდ ამ ელემენტს დავბეჭდავთ.

ალგორითმი

  1. გაუშვით I მარყუჟი 0-დან n-1 დიაპაზონში
    1. აწარმოეთ მარყუჟი j- სთვის 0-დან n -მდე
      1. თუ j ტოლი გახდება n, მაშინ ამობეჭდეთ A [i] და დააბრუნეთ.
      2. თუ I არ არის ტოლი j და A [i] უდრის A [j], მაშინ გაწყვეტ ამ მარყუჟს.
    2. დაბეჭდეთ, რომ ყველა ელემენტი იმეორებს მასივს.

განხორციელება პირველი არა განმეორებითი ელემენტისთვის

C ++ პროგრამა

#include <bits/stdc++.h>
using namespace std;
void firstNonRepeatingElement(vector<int> &A)
{
    int n = A.size();
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            if (j == n)
            {
                cout << "First non-repeating element is: " << A[i] << endl;
                return;
            }
            if (j != i and A[i] == A[j])
            {
                break;
            }
        }
    }
    cout << "All the elements are repeating." << endl;
}
int main()
{
    vector<int> A = {2, 1, 2, 1, 3, 4};
    firstNonRepeatingElement(A);
    return 0;
}
First non-repeating element is: 3

JAVA პროგრამა

public class Main
{
    static void firstNonRepeatingElement(int A[])
    {
        int n = A.length;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j <= n; j++)
            {
                if (j == n)
                {
                    System.out.println("First non-repeating element is: "+A[i]);
                    return;
                }
                if (j != i && A[i] == A[j])
                {
                    break;
                }
            }
        }
        System.out.println("All the elements are repeating.");
    }
  public static void main(String[] args) {
    int A[]={2, 1, 2, 1, 3, 4};
    firstNonRepeatingElement(A);
  }
}
First non-repeating element is: 3

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

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

ჩვენ გვაქვს ორი ჩადგმული მარყუჟი, რომელთა ზომაც N არის, ამიტომ სირთულის დროა O (N ^ 2).

კოსმოსური სირთულის

ჩვენ არ ვიყენებთ რაიმე დამატებით ადგილს, ამიტომ სივრცის სირთულე არის O (1).

მიდგომა 2: ჰეშირების გამოყენება

Მთავარი იდეა

ჩვენ შეგვიძლია შევინახოთ თითოეული ელემენტის სიხშირე ჰეშის ცხრილში და ამის შემდეგ შეგვიძლია მასივის გავლა და ვიპოვოთ პირველი ელემენტი, რომლის სიხშირეა 1.

ალგორითმი

  1. შეინახეთ თითოეული ელემენტის სიხშირე ჰეშის ცხრილში.
  2. გაუშვით I მარყუჟი 0-დან n-1 დიაპაზონში
    1. თუ ჰეშის ცხრილში A [i] - ის სიხშირეა 1, დაბეჭდე A [i] და დააბრუნე.
  3. დაბეჭდეთ მასში მასივის ყველა ელემენტი, რომლებიც მეორდება.

გაიგე მაგალითით

A [] = {2, 1, 2, 1, 3, 4}

შემდეგ ჰეშის მაგიდა ასე გამოიყურება:

პირველი არა განმეორებადი ელემენტი

განხორციელება პირველი არა განმეორებითი ელემენტისთვის

C ++ პროგრამა

#include <bits/stdc++.h>
using namespace std;
void firstNonRepeatingElement(vector<int> &A)
{
    int n = A.size();
    unordered_map<int, int> hash_table;
    for (int i = 0; i < n; i++)
    {
        hash_table[A[i]]++;
    }
    for (int i = 0; i < n; i++)
    {
        if (hash_table[A[i]] == 1)
        {
            cout << "First non-repeating element is: " << A[i] << endl;
            return;
        }
    }
    cout << "All the elements are repeating." << endl;
}
int main()
{
    vector<int> A = {2, 1, 2, 1, 3, 4};
    firstNonRepeatingElement(A);
    return 0;
}
First non-repeating element is: 3

JAVA პროგრამა

public class Main
{
    static void firstNonRepeatingElement(int A[])
    {
        java.util.HashMap<Integer, Integer> hash_table = new java.util.HashMap<Integer, Integer>();
        int n = A.length;
        for(int i=0;i<n;i++)
        {
            Integer freq = hash_table.get(A[i]);
            hash_table.put(A[i], (freq == null) ? 1 : freq + 1); 
        }

        for (int i = 0; i < n; i++)
        {
            if (hash_table.get(A[i])==1)
            {
                System.out.println("First non-repeating element is: "+A[i]);
                return;
            }
        }
        System.out.println("All the elements are repeating.");
    }
  public static void main(String[] args) {
    int A[]={2, 1, 2, 1, 3, 4};
    firstNonRepeatingElement(A);
  }
}
First non-repeating element is: 3

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

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

ჩვენ მასივს მხოლოდ ორჯერ ვაკეთებთ, ასე რომ მთლიანი დროის სირთულეა O (N).

კოსმოსური სირთულის

ჩვენ ვინახავთ ჰაში მაგიდას, ასე რომ სივრცის სირთულეა O (N).

ლიტერატურა