మొదటి పునరావృతం కాని మూలకం


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది బెల్జాబర్ కొమ్లి మీడియా మెట్ లైఫ్ స్నాప్డీల్ స్ప్రింక్లర్ వూకర్
అర్రే హాష్ శోధించండి

మాకు శ్రేణి A. ఇవ్వబడింది. మేము శ్రేణిలో మొదటి పునరావృతం కాని మూలకాన్ని కనుగొనాలి.

ఉదాహరణ

ఇన్పుట్:

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

అవుట్పుట్:

మొదటి పునరావృతం కాని మూలకం: 3

ఎందుకంటే 1, 2 సమాధానం కాదు ఎందుకంటే అవి పునరావృతమవుతున్నాయి మరియు 4 సమాధానం కాదు ఎందుకంటే మనం మొదటి నాన్-రిపీటింగ్ ఎలిమెంట్‌ను కనుగొనవలసి ఉంది, ఇది 3, 4 కాదు.

అప్రోచ్ 1: బ్రూట్ ఫోర్స్

ప్రధానమైన ఆలోచన

లోని ప్రతి మూలకం కోసం అమరిక, మేము మొత్తం శ్రేణిని మళ్ళిస్తాము మరియు ఈ మూలకం పునరావృతం కాకపోతే ఈ మూలకాన్ని ప్రింట్ చేస్తాము.

అల్గారిథం

  1. 0 నుండి n-1 పరిధిలో నేను కోసం ఒక లూప్‌ను అమలు చేయండి
    1. 0 నుండి n పరిధిలో j కోసం లూప్‌ను అమలు చేయండి
      1. J n కు సమానంగా మారితే, A [i] ను ప్రింట్ చేసి తిరిగి వెళ్ళు.
      2. నేను j కి సమానం కాకపోతే మరియు A [i] A [j] కు సమానం అయితే, అప్పుడు ఈ లూప్ నుండి విచ్ఛిన్నం.
    2. శ్రేణిలో అన్ని అంశాలు పునరావృతమవుతున్నాయని ముద్రించండి.

మొదటి పునరావృతం కాని మూలకం కోసం అమలు

సి ++ ప్రోగ్రామ్

#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

జావా ప్రోగ్రామ్

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. 0 నుండి n-1 పరిధిలో నేను కోసం ఒక లూప్‌ను అమలు చేయండి
    1. హాష్ పట్టికలో A [i] యొక్క పౌన frequency పున్యం 1 అయితే, A [i] ను ముద్రించి తిరిగి వెళ్ళు.
  3. శ్రేణిలోని అన్ని అంశాలు పునరావృతమవుతున్నాయని ముద్రించండి.

ఉదాహరణతో అర్థం చేసుకోండి

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

అప్పుడు హాష్ పట్టిక ఇలా ఉంటుంది:

మొదటి పునరావృతం కాని మూలకం

మొదటి పునరావృతం కాని మూలకం కోసం అమలు

సి ++ ప్రోగ్రామ్

#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

జావా ప్రోగ్రామ్

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

మొదటి పునరావృతం కాని మూలకం కోసం సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

మేము శ్రేణిని రెండుసార్లు మాత్రమే మళ్ళిస్తున్నాము కాబట్టి మొత్తం సమయం సంక్లిష్టత పై).

స్థల సంక్లిష్టత

మేము హాష్ పట్టికను నిర్వహిస్తున్నాము కాబట్టి స్థలం సంక్లిష్టత పై).

ప్రస్తావనలు