శ్రేణి లీట్‌కోడ్ పరిష్కారంలో రెండు మూలకాల గరిష్ట ఉత్పత్తి


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

“శ్రేణిలో రెండు మూలకాల గరిష్ట ఉత్పత్తి” సమస్యలో, రెండు సూచికలను కనుగొనడం మా లక్ష్యం i మరియు j ఇచ్చిన పూర్ణాంకాల శ్రేణిలో a, ఉత్పత్తి (a [i] - 1) * (a [j] - 1) గరిష్టంగా ఉంటుంది. శ్రేణికి కనీసం 2 అంశాలు ఉన్నాయి మరియు అన్ని అంశాలు సానుకూలంగా ఉంటాయి. అవసరమైన ఉత్పత్తి పూర్ణాంక పరిధిలో సరిపోయే సమస్య. మేము సరైన (a [i] - 1) * (a [j] - 1) విలువను ప్రింట్ చేయాలి i & j.

విషయ సూచిక

ఉదాహరణ

a = {1 , 4 , 5 , 3 , 6 , 4}
2

వివరణ

స్పష్టంగా, 6 మరియు 5 అతిపెద్ద మరియు రెండవ అతిపెద్ద సంఖ్యలు. కాబట్టి, ఉత్పత్తి = (a [i] - 1) * (a [j] - 1) = 20.

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

వస్తువు: (a [i] - 1) * (a [j] - 1) [i] మరియు [j] శ్రేణిలోని రెండు అతిపెద్ద అంశాలు అయినప్పుడు గరిష్టంగా ఉంటుంది. రెండు గొప్ప అంశాలను కలిగి ఉన్న i మరియు j అనే రెండు సూచికలను కనుగొనటానికి బదులుగా, మనం చేయవచ్చు విధమైన ది అమరిక ఆరోహణ క్రమంలో. ఇది రెండు అతిపెద్ద అంశాలు చివరిలో ఉన్నాయని నిర్ధారిస్తుంది. అందువల్ల, ఉత్పత్తి (a [n - 1] - 1) * (a [n - 2] - 1) అవసరమైన ఫలితం అవుతుంది.

అల్గారిథం

  1. శ్రేణిని క్రమబద్ధీకరించండి
  2. ఫలితాన్ని ముద్రించండి: (a [n - 1] - 1) * (a [n - 2] - 1)

శ్రేణిలో రెండు మూలకాల గరిష్ట ఉత్పత్తిని కనుగొనడానికి అల్గోరిథం అమలు

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

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

int maxProduct(vector <int> &a)
{
    int n = a.size();
    sort(a.begin() , a.end());
    return ((a[n - 1] - 1) * (a[n - 2] - 1));
}


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

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

import java.util.Arrays;

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

    static int maxProduct(int[] a)
    {
        int n = a.length;
        Arrays.sort(a);
        return (a[n - 1] - 1) * (a[n - 2] - 1);
    }
}
20

శ్రేణిలో రెండు మూలకాల యొక్క గరిష్ట ఉత్పత్తిని కనుగొనడంలో సంక్లిష్టత విశ్లేషణ

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

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

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

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

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

మేము పైన చర్చించినట్లుగా, శ్రేణిలోని రెండు గొప్ప అంశాలను కనుగొనాలి. మొత్తం శ్రేణిని క్రమబద్ధీకరించడం ద్వారా, మేము ఓవర్డో అవసరమైన పని. కాబట్టి, సరళమైన పోలిక కార్యకలాపాల ద్వారా శ్రేణిలో మొదటి మరియు రెండవ అతిపెద్ద మూలకాన్ని కనుగొనడం సరైనది. అందువల్ల, అవసరమైన ఫలితాన్ని పొందవచ్చు (ఫస్ట్‌మాక్స్ - 1) * (సెకండ్‌మాక్స్ - 1).

శ్రేణి లీట్‌కోడ్ పరిష్కారంలో రెండు మూలకాల గరిష్ట ఉత్పత్తి

అల్గారిథం

  1. రెండు వేరియబుల్స్ ప్రారంభించండి: ఫస్ట్‌మాక్స్ మరియు సెకండ్‌మాక్స్ సున్నాగా (తద్వారా శ్రేణిలోని ఏదైనా విలువ వాటిని అంతర్గతంగా నవీకరిస్తుంది).
  2. శ్రేణి ప్రారంభం నుండి దాని చివరి వరకు లూప్‌ను అమలు చేయండి.
  3. ప్రతి మూలకం కోసం:
    • ఇది ఫస్ట్‌మాక్స్ కంటే ఎక్కువగా ఉందో లేదో తనిఖీ చేయండి:
      • నిజమైతే:
        • SecondMax = firstMax ని సెట్ చేయండి
        • ఫస్ట్‌మాక్స్ = ప్రస్తుత-మూలకాన్ని నవీకరించండి
      • లేకపోతే:
        • ఇది సెకండ్‌మాక్స్ కంటే ఎక్కువగా ఉంటే
          • సెకండ్‌మాక్స్ = ప్రస్తుత-మూలకాన్ని నవీకరించండి
  4. ఫలితాన్ని ముద్రించండి

అర్రే లీట్‌కోడ్ సొల్యూషన్‌లో రెండు ఎలిమెంట్స్ యొక్క గరిష్ట ఉత్పత్తిని కనుగొనడానికి అల్గోరిథం అమలు

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

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

int maxProduct(vector <int> &a)
{
    int firstMax = 0 , secondMax = 0 , n = a.size();
    for(int i = 0 ; i < n ; i++)
        if(a[i] > firstMax)
        {
            secondMax = firstMax;
            firstMax = a[i];
        }
        else if(a[i] > secondMax)
            secondMax = a[i];

    return (firstMax - 1) * (secondMax - 1);
}

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

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

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

    static int maxProduct(int[] a)
    {
        int firstMax = 0 , secondMax = 0 , n = a.length;
        for(int i = 0 ; i < n ; i++)
            if(a[i] > firstMax)
            {
                secondMax = firstMax;
                firstMax = a[i];
            }
            else if(a[i] > secondMax)
                secondMax = a[i];

        return (firstMax - 1) * (secondMax - 1);
    }
}
20

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

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

O (N), N = శ్రేణి యొక్క పరిమాణం. సాధారణ పోలిక కార్యకలాపాల కోసం మేము సరళ లూప్‌ను అమలు చేస్తాము.

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

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