X ఎలిమెంట్స్‌తో గ్రేటర్ కంటే ఎక్కువ లేదా సమానమైన X లీట్‌కోడ్ సొల్యూషన్‌తో ప్రత్యేక శ్రేణి


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది గూగుల్
అర్రే హ్యాషింగ్

సమస్యలో, “స్పెషల్ అర్రే విత్ ఎక్స్ ఎలిమెంట్స్ గ్రేటర్ దన్ లేదా ఈక్వల్ ఎక్స్”, మాకు ఇవ్వబడింది అమరిక నాన్-నెగటివ్ పూర్ణాంకాల. శ్రేణిలో దాని కంటే ఎక్కువ లేదా సమానమైన X మూలకాలు ఉన్న కొన్ని పూర్ణాంక X ను మనం కనుగొనాలి. ఈ పరిస్థితిని సంతృప్తిపరిచే X లేకపోతే, మేము అవుట్పుట్ -1 చేయాలి.

విషయ సూచిక

ఉదాహరణ

1 2 3 4
-1
1 3 4 5
3

అప్రోచ్ (బ్రూట్ ఫోర్స్)

X పరిష్కారం ఉంటే అది ఖచ్చితంగా X ఎల్లప్పుడూ ప్రత్యేకంగా ఉంటుంది.

రుజువు:

X! Y అనే రెండు పరిష్కారాలు ఉన్నాయని పరిగణించండి. X! = Y. X <Y అని అనుకుందాం. ఇప్పుడు, X కంటే ఎక్కువ లేదా సమానమైన మూలకాల సంఖ్య X గా ఉండాలి. కానీ, Y> X నుండి, X కంటే ఎక్కువ లేదా సమానమైన Y మూలకాలు ఉన్నాయి! X! = Y. అందువల్ల X మరియు Y సమానంగా ఉంటే తప్ప X ఒక పరిష్కారం అని మన wrong హ తప్పు.

కాబట్టి, ఒక పరిష్కారం ఉంటే, ఎల్లప్పుడూ ఒక ప్రత్యేకమైన పరిష్కారం ఉంటుంది. ఇప్పుడు, X అనేది ఒక పరిష్కారం అయితే, దానికి సమానమైన / సమానమైన మూలకాల సంఖ్య = X, ఇది N కన్నా తక్కువ ఉండాలి, ఇక్కడ శ్రేణి యొక్క N = పరిమాణం (సాధ్యమయ్యే గరిష్ట మూలకాల సంఖ్య = ఎన్).

కాబట్టి, X పరిష్కారం ఉంటే, అది [1, N] పరిధిలో ఉండాలి.

శ్రేణిలోని ఏదైనా పూర్ణాంకం కంటే ఎక్కువ లేదా సమానమైన శ్రేణిలోని మూలకాల సంఖ్య ఆ పూర్ణాంకానికి సమానంగా ఉంటే మేము పరిధిలోని ప్రతి పూర్ణాంకం కోసం తనిఖీ చేయవచ్చు [1, N]. ఉదాహరణకు, అర్రే = {1, 3, 4, 5 consider ను పరిగణించండి. ఇప్పుడు, 1 మరియు 2 వరుసగా 4 మరియు 3 మూలకాలను శ్రేణిలో వాటి కంటే ఎక్కువ లేదా సమానంగా కలిగి ఉంటాయి. 3 = 3 కంటే ఎక్కువ / సమానమైన మూలకాల సంఖ్య. కాబట్టి, 3 మాత్రమే పరిష్కారం. పరిధిలోని ప్రతి పూర్ణాంకం కంటే ఎక్కువ మూలకాల సంఖ్యను కనుగొనడానికి మేము మొత్తం చెట్టును దాటుతున్నందున: [1, N], ఈ విధానం నెమ్మదిగా ఉంటుంది.

అల్గారిథం

  1. పరిష్కారం కోసం తనిఖీ చేయడానికి i = 1 నుండి i = N వరకు లూప్‌ను అమలు చేయండి:
    • 'కంటే ఎక్కువ లేదా సమానమైన మూలకాల సంఖ్యను లెక్కించండిi'శ్రేణిలో
      • లెక్కింపు సమానంగా ఉంటే 'i', తిరిగి నేను
  2. రిటర్న్ -1;

X ఎలిమెంట్స్‌తో గ్రేటర్ కంటే ఎక్కువ లేదా సమానమైన X లీట్‌కోడ్ సొల్యూషన్‌తో ప్రత్యేక శ్రేణి అమలు

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

#include <bits/stdc++.h>
using namespace std;

int specialArray(vector <int> &a)
{
    int n = a.size() , counter = 0;
    for(int i = 1 ; i <= n ; i++)
    {
        counter = 0;
        for(int j = 0 ; j < n ; j++)
            if(a[j] >= i)
                counter++;
        if(counter == i)
            return i;
    }
    return -1;
}

int main()
{
    vector <int> a = {1 , 3 , 4 , 5};
    cout << specialArray(a) << '\n';
}

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

class special_array
{
    public static void main(String args[])
    {
        int[] a = {1 , 3 , 4 , 5};
        System.out.println(specialArray(a));
    }

    static int specialArray(int[] a)
    {
        int n = a.length , counter = 0;
        for(int i = 1 ; i <= n ; i++)
        {
            counter = 0;
            for(int j = 0 ; j < n ; j++)
                if(a[j] >= i)
                    counter++;
            if(counter == i)
                return i;
        }
        return -1;
    }
}
3

X ఎలిమెంట్స్‌తో గ్రేట్ లేదా సమానమైన X లీట్‌కోడ్ సొల్యూషన్‌తో ప్రత్యేక శ్రేణి యొక్క సంక్లిష్టత విశ్లేషణ

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

O (N * N), N = శ్రేణి యొక్క పరిమాణం. చెత్త సందర్భంలో, X = N పరిష్కారం అయినప్పుడు, మేము O (N * N) పోలికలను చేస్తాము.

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

O (1). స్థిరమైన మెమరీ స్థలం మాత్రమే ఉపయోగించబడుతుంది.

అప్రోచ్ (ఆప్టిమల్)

మేము శ్రేణిని ఉపయోగించి పట్టికలో అన్ని మూలకాల సంభవించిన సంఖ్యలను నిల్వ చేయవచ్చు. N కంటే ఎక్కువ విలువ కలిగిన ఏదైనా మూలకం కోసం, మేము దానిని N విలువ కలిగిన మూలకం యొక్క సంఘటనగా పరిగణించవచ్చు ఎందుకంటే పరిష్కారం యొక్క గరిష్ట విలువ N కావచ్చు.

ఇప్పుడు, X కంటే ఎక్కువ లేదా సమానమైన మూలకాల యొక్క ఫ్రీక్వెన్సీ X కంటే ఎక్కువ అన్ని మూలకాల యొక్క X + ఫ్రీక్వెన్సీ. [1, N] పరిధిలోని ప్రతి మూలకం కోసం దీనిని కనుగొనడానికి, మనకు ప్రత్యయం ఫ్రీక్వెన్సీ శ్రేణి ఉండాలి .

కాబట్టి, శ్రేణిలోని ప్రతి పూర్ణాంకం కోసం, మేము సెట్ చేయాలి ఫ్రీక్వెన్సీ [i] = ఫ్రీక్వెన్సీ [i] + ఫ్రీక్వెన్సీ [i + 1], ప్రతి కోసం 'i'పరిధిలో [N - 1, 1], ఇది ప్రత్యయం ఫ్రీక్వెన్సీ శ్రేణిని సృష్టిస్తుంది, ఎక్కువ లేదా అంతకంటే ఎక్కువ మూలకాల సంఖ్యను నిల్వ చేస్తుంది 'i'  as పౌన frequency పున్యం [i].

ఇప్పుడు, శోధన పట్టిక కారణంగా, [1, N] పరిధిలోని ఏదైనా పూర్ణాంకం కోసం మేము ఒక పరిష్కారాన్ని తనిఖీ చేయవచ్చు O (1) సమయం. ఇది మనం ఉన్న సందర్భం వర్తకం సమయానికి మెరుగుపరచడానికి మెమరీ. పట్టిక పరిమాణం N గా ఉన్నందున, మనకు మెమరీ పరిమితుల గురించి కూడా చింత లేదు.

 

X ఎలిమెంట్స్‌తో గ్రేటర్ కంటే ఎక్కువ లేదా సమానమైన X లీట్‌కోడ్ సొల్యూషన్‌తో ప్రత్యేక శ్రేణి

అల్గారిథం

  1. ప్రారంభించండి a తరచుదనం పరిమాణం N యొక్క శ్రేణి, ప్రతి విలువను కలిగి ఉంటుంది సున్నా
  2. ప్రతి మూలకం కోసం i  శ్రేణిలో:
    1. If i > N, ఇంక్రిమెంట్ ఫ్రీక్వెన్సీ [N]
    2. పెరుగుదల పౌన frequency పున్యం [i]
  3. నుండి ప్రత్యయం మొత్తం శ్రేణిని సృష్టించండి తరచుదనం వంటి:
    1. నుండి ప్రతి మూలకం కోసం i = ఎన్ - 1 కు i = 0
      1. సెట్ తరచుదనం[i] = పౌన frequency పున్యం [i] + ఫ్రీక్వెన్సీ [i + 1]
  4. నుండి లూప్‌ను అమలు చేయండి i = 1 నుండి i = N
    1. If i == పౌన frequency పున్యం [i], తిరిగి i
  5. తిరిగి -1

X ఎలిమెంట్స్‌తో గ్రేటర్ కంటే ఎక్కువ లేదా సమానమైన X లీట్‌కోడ్ సొల్యూషన్‌తో ప్రత్యేక శ్రేణి అమలు

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

#include <bits/stdc++.h>
using namespace std;

int specialArray(vector<int>& a)
{
    int n = a.size();
    vector <int> frequency(n + 1 , 0);
    for(int i = 0 ; i < n ; i++)
        if(a[i] > n)
            frequency[n]++;
        else
            frequency[a[i]]++;

    for(int i = n - 1 ; i >= 0 ; i--)
        frequency[i] += frequency[i + 1];

    for(int i = 0 ; i <= n ; i++)
        if(frequency[i] == i)
            return i;

    return -1;
}

int main()
{
    vector <int> a = {1 , 3 , 4 , 5};
    cout << specialArray(a) << '\n';
}

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

class special_array
{
    public static void main(String args[])
    {
        int[] a = {1 , 3 , 4 , 5};
        System.out.println(specialArray(a));
    }

    static int specialArray(int[] a)
    {
        int n = a.length;
        int[] frequency = new int[n + 1];
        for(int i = 0 ; i < n ; i++)
            frequency[i] = 0;

        for(int i = 0 ; i < n ; i++)
            if(a[i] > n)
                frequency[n]++;
            else
                frequency[a[i]]++;

        for(int i = n - 1 ; i >= 0 ; i--)
            frequency[i] += frequency[i + 1];

        for(int i = 0 ; i <= n ; i++)
            if(frequency[i] == i)
                return i;

        return -1;
    }
}
3

X ఎలిమెంట్స్‌తో గ్రేట్ లేదా సమానమైన X లీట్‌కోడ్ సొల్యూషన్‌తో ప్రత్యేక శ్రేణి యొక్క సంక్లిష్టత విశ్లేషణ

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

పై), N = శ్రేణి యొక్క పరిమాణం. మేము O (1) సమయంలో ఏదైనా పూర్ణాంకం కోసం తనిఖీ చేయవచ్చు, కాబట్టి చెత్త సందర్భంలో, మేము O (N) సమయాన్ని ఉపయోగిస్తాము.

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

పై). ఫ్రీక్వెన్సీలను నిల్వ చేయడానికి లీనియర్ మెమరీ స్థలం ఉపయోగించబడుతుంది.