మూడవ గరిష్ట సంఖ్య లీట్‌కోడ్ పరిష్కారం


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది అమెజాన్ <span style="font-family: Mandali; ">ఫేస్‌బుక్ </span> గూగుల్
అర్రే

టైటిల్ చెప్పినట్లుగా, ఇచ్చిన వాటిలో మూడవ గరిష్ట పూర్ణాంకాన్ని కనుగొనడం లక్ష్యం అమరిక పూర్ణాంకాల. మేము కనుగొనవలసి ఉందని గమనించండి విభిన్న శ్రేణిలో మూడవ గరిష్ట పూర్ణాంకం. ప్రత్యేకమైన గరిష్ట గరిష్ట పూర్ణాంకం లేనప్పుడు మేము శ్రేణిలోని గరిష్ట పూర్ణాంకాన్ని తిరిగి ఇస్తాము.

ఉదాహరణ

Array = {1 , 3 , 2 , -2 , -4 , -9}
1

వివరణ

మొదటి గరిష్ట 3, రెండవ గరిష్ట 2 మరియు మూడవ గరిష్ట 1. కాబట్టి, మేము 1 ను ప్రింట్ చేస్తాము.

Array = {1 , 1 , 3}
3

వివరణ

మొదటి గరిష్ట 3, రెండవ గరిష్ట 1, కానీ ఉంది మూడవ గరిష్టం ఎందుకంటే మేము 1 సె రెండింటినీ ఇక్కడ రెండవ గరిష్టంగా పరిగణిస్తాము.

అప్రోచ్ (సార్టింగ్)

మేము మొత్తం శ్రేణిని క్రమబద్ధీకరించవచ్చు మరియు కనుగొనవచ్చు మూడవ ప్రత్యేకత పూర్ణాంకం దాని నుండి ప్రారంభమవుతుంది తిరిగి. శ్రేణిలో నకిలీ ఎంట్రీలు ఉన్నందున మేము అర్రే [N - 3] ను తిరిగి ఇవ్వలేమని గమనించండి. మేము కనుగొనలేకపోతే 3 శ్రేణిలో విభిన్న పూర్ణాంకాలు, గరిష్ట మూలకం కనుక మేము దాని చివరి మూలకాన్ని తిరిగి ఇస్తాము. మంచి అవగాహన కోసం ఇచ్చిన అల్గోరిథంను అనుసరించండి.

మూడవ గరిష్ట సంఖ్య లీట్‌కోడ్ పరిష్కారం

అల్గారిథం

  1. ఒక ఫంక్షన్ సృష్టించండి థర్డ్ మాక్స్ () అవసరమైన పూర్ణాంకాన్ని తిరిగి ఇస్తుంది
  2. థర్డ్ మాక్స్ () ఇచ్చిన శ్రేణిలో మూడవ విభిన్న గరిష్ట పూర్ణాంకాన్ని అందిస్తుంది- a
  3. శ్రేణిని క్రమబద్ధీకరించండి
  4. వేరియబుల్ ప్రారంభించండి, idx శ్రేణి యొక్క చివరి సూచికను నిల్వ చేయడానికి మరియు విభిన్న గణన వెనుక నుండి విభిన్న అంశాలను లెక్కించడానికి
  5. అయితే idx> = 0:
    • ఇంక్రిమెంట్ విభిన్న గణన
    • ప్రారంభించును [idx] కు సమానమైన విలువ కలిగిన సూచికల ద్వారా మళ్ళించడానికి
    • ముందు అంశాలు idx [idx] మరియు అదే విలువను కలిగి ఉంటుంది i> = 0:
      • తగ్గుదల i
    • If i == -1, దీని అర్థం మనం మొత్తం శ్రేణిని దాటినట్లు
      • శ్రేణిలో 1 మూడు విభిన్న అంశాలు కూడా లేనందున [n - 3], గరిష్ట మూలకాన్ని తిరిగి ఇవ్వండి
    • కేటాయించవచ్చు idx = i గరిష్ట పూర్ణాంకాల తదుపరి సెట్‌కి వెళ్లడానికి
    • If విభిన్న గణన 2 కు సమానం,
      • అంటే ప్రస్తుత మూలకం (a [idx]) కంటే 2 పెద్ద మూలకాలను మేము తనిఖీ చేసాము.
      • ప్రస్తుత మూలకాన్ని తిరిగి ఇవ్వండి, [idx]
  6.  ఫంక్షన్ సింటాక్స్ కొరకు, తిరిగి -1.
  7. ఫలితాన్ని ముద్రించండి

మూడవ గరిష్ట సంఖ్య లీట్‌కోడ్ పరిష్కారం అమలు

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

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

int thirdMax(vector <int> &a)
{
    int n = a.size();
    sort(a.begin() , a.end());

    int idx = n - 1 , i , distinctCount = 0;

    while(idx >= 0)
    {
        distinctCount++;
        i = idx - 1;
        //to check all the values with same value as a[idx]
        while(i >= 0 && a[i] == a[idx])
            i--;

        //no third distinct element
        if(i == -1)
            return a[n - 1];
        idx = i;

        //found 2 bigger elements before?
        if(distinctCount == 2)
            return a[idx];
    }
    return -1;
}

int main()
{
    vector <int> a = {1 , 3 , 2 , -2 , -4 , -9};
    cout << thirdMax(a) << '\n';
}

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

import java.util.Arrays;

class third_max
{
    public static void main(String args[])
    {
        int[] a = {1 , 3 , 2 , -2 , -4 , -9};
        System.out.println(thirdMax(a));
    }

    static int thirdMax(int[] a)
    {
        int n = a.length;
        Arrays.sort(a);

        int idx = n - 1 , i , distinctCount = 0;

        while(idx >= 0)
        {
            distinctCount++;
            i = idx - 1;
            //to check all the values with same value as a[idx]
            while(i >= 0 && a[i] == a[idx])
                i--;

            //no third distinct element
            if(i == -1)
                return a[n - 1];
            idx = i;

            //found 2 bigger elements before?
            if(distinctCount == 2)
                return a[idx];
        }
        return -1;
    }
}
1

మూడవ గరిష్ట సంఖ్య లీట్‌కోడ్ పరిష్కారం యొక్క సంక్లిష్టత విశ్లేషణ

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

O (NlogN), N = శ్రేణి యొక్క పరిమాణం, మేము మొత్తం శ్రేణిని క్రమబద్ధీకరించినప్పుడు.

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

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

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

శ్రేణిలో మొదటి, రెండవ మరియు మూడవ గరిష్ట పూర్ణాంకాలను నిల్వ చేసే కేవలం మూడు విలువలను నిర్వహించడం ఇక్కడ సరైన విధానం. ఏదేమైనా, కొన్ని మూల కేసులు ఉన్నాయి, ఎందుకంటే మేము ఎల్లప్పుడూ విభిన్న అంశాలను గరిష్టంగా పరిగణించాలి. ఈ ప్రయోజనం కోసం, సెట్ మేము ఎల్లప్పుడూ నకిలీ మూలకాలను వదిలించుకోవడానికి వీలుగా ఉపయోగించవచ్చు. మేము శ్రేణి ద్వారా మళ్ళించవచ్చు మరియు పరిమాణాన్ని నిర్వహించవచ్చు సెట్ ప్రతి పునరావృతం తర్వాత 3 గా. ఏదైనా చొప్పించిన తర్వాత అది 3 కంటే ఎక్కువ మూలకాలను కలిగి ఉంటే, మేము దాని నుండి అతి తక్కువ మూలకాన్ని పాప్ అవుట్ చేస్తాము, తద్వారా అది మూడింటిని కలిగి ఉంటుంది విభిన్నమైన అతిపెద్దది చివరికి మూలకాలు. చివరికి దాని పరిమాణం 3 కన్నా తక్కువ ఉంటే, మేము దాని గరిష్ట విలువను తిరిగి ఇస్తాము.

అల్గారిథం

  1. మళ్ళీ మేము అదే ఫంక్షన్ ఉపయోగిస్తాము థర్డ్ మాక్స్ () మా సమస్యను పరిష్కరించడానికి
  2. గరిష్ట పూర్ణాంకాలను నిల్వ చేయడానికి సమితిని ప్రారంభించండి.
  3. ప్రతి కోసం మూలకం శ్రేణిలో:
    • సెట్‌కు జోడించండి
    • సెట్ యొక్క పరిమాణం 3 మించి ఉంటే
      • సెట్‌లోని అతి తక్కువ మూలకాన్ని తొలగించండి / తొలగించండి
  4. సెట్ యొక్క పరిమాణం 3 కి సమానంగా ఉంటే
    • దాని నుండి కనీస మూలకాన్ని తిరిగి ఇవ్వండి
  5. వేరే
    • దానిలోని గరిష్ట మూలకాన్ని తిరిగి ఇవ్వండి
  6. ఫలితాన్ని ముద్రించండి

మూడవ గరిష్ట సంఖ్య లీట్‌కోడ్ పరిష్కారం అమలు

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

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

int thirdMax(vector <int> &a)
{
    set <int> maxElements;
    for(int &element : a)
    {
        maxElements.insert(element);
        if(maxElements.size() > 3)
            maxElements.erase(*maxElements.begin());
    }
    if(maxElements.size() == 3)
        return *maxElements.begin();

    return *prev(maxElements.end());
}

int main()
{
    vector <int> a = {1 , 3 , 2 , -2 , -4 , -9};
    cout << thirdMax(a) << '\n';
}

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

import java.util.*;

class third_max
{
    public static void main(String args[])
    {
        int[] a = {1 , 3 , 2 , -2 , -4 , -9};
        System.out.println(thirdMax(a));
    }

    static int thirdMax(int[] a)
    {
        Set <Integer> maxElements = new HashSet <>();
        for(int element : a)
        {
            maxElements.add(element);
            if(maxElements.size() > 3)
                maxElements.remove(Collections.min(maxElements));
        }

        if(maxElements.size() == 3)
            return Collections.min(maxElements);
        return Collections.max(maxElements);
    }
}
1

మూడవ గరిష్ట సంఖ్య లీట్‌కోడ్ పరిష్కారం యొక్క సంక్లిష్టత విశ్లేషణ

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

పై) మేము ఒకే పాస్లో శ్రేణి ద్వారా మళ్ళిస్తాము. సెట్‌లోని మూలకాల తొలగింపు మరియు చొప్పించడం స్థిరమైన సమయం పడుతుంది, ఎందుకంటే ప్రతి పునరావృతం తర్వాత మేము గరిష్టంగా 3 మూలకాలను కలిగి ఉంటాము. ఇక్కడ, N = శ్రేణి యొక్క పరిమాణం.

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

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