अ‍ॅरे लीटकोड सोल्यूशनमध्ये दोन घटकांचे जास्तीत जास्त उत्पादन


अडचण पातळी सोपे
वारंवार विचारले सॅमसंग
अरे

“अ‍ॅरेमधील दोन घटकांचे जास्तीत जास्त उत्पादन” या समस्येमध्ये दोन निर्देशांक शोधण्याचे आपले लक्ष्य आहे 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) अ‍ॅर मधील दोन [i] आणि [[]] दोन सर्वात मोठे घटक असल्यास जास्तीत जास्त असेल. दोन महान घटक असलेले दोन निर्देशांक i आणि j शोधण्याऐवजी आम्ही ते करू शकतो क्रमवारी अगोदर निर्देश केलेल्या बाबीसंबंधी बोलताना अॅरे चढत्या क्रमाने. हे सुनिश्चित करेल की दोन सर्वात मोठे घटक शेवटी आहेत. म्हणून, उत्पादन (अ [एन - १] - १) * (अ [एन - २] - १) आवश्यक परिणाम होईल.

अल्गोरिदम

  1. अ‍ॅरेची क्रमवारी लावा
  2. परिणाम मुद्रित करा: (एक [एन - 1] - 1) * (अ [एन - 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) वेळ घेणार्‍या अ‍ॅरेची क्रमवारी आम्ही करतो.

जागेची जटिलता

ओ (1)आपण सतत मेमरी स्पेस वापरत आहोत.

दृष्टीकोन (इष्टतम)

आम्ही वर चर्चा केल्याप्रमाणे, अ‍ॅरेमधील दोन महान घटक शोधणे आवश्यक आहे. संपूर्ण अ‍ॅरेची क्रमवारी लावून आम्ही प्रमाणा बाहेर आवश्यक काम. तर, सोप्या तुलनेत ऑपरेशन्सद्वारे अ‍ॅरेमधील पहिला आणि दुसरा सर्वात मोठा घटक शोधणे इष्टतम आहे. म्हणूनच, आवश्यक परिणाम म्हणून मिळू शकतो (फर्स्टमॅक्स - 1) * (सेकंडमॅक्स - 1).

अ‍ॅरे लीटकोड सोल्यूशनमध्ये दोन घटकांचे जास्तीत जास्त उत्पादन

अल्गोरिदम

  1. दोन व्हेरिएबल्स आरंभ कराः फर्स्टमॅक्स आणि सेकंडमॅक्स शून्य (जेणेकरून अ‍ॅरेमधील कोणतेही मूल्य त्यांना अंतर्भूतपणे अद्यतनित करते).
  2. अ‍ॅरेच्या सुरुवातीपासून शेवटपर्यंत लूप चालवा.
  3. प्रत्येक घटकासाठी:
    • ते फर्स्टमॅक्सपेक्षा मोठे आहे का ते तपासा:
      • सत्य असल्यास:
        • सेकंदमॅक्स = फर्स्टमॅक्स सेट करा
        • फर्स्टमॅक्स = वर्तमान-घटक अद्यतनित करा
      • अन्यथा:
        • हे सेकंडमॅक्सपेक्षा मोठे असल्यास
          • सेकंडमॅक्स = चालू-घटक अद्यतनित करा
  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

अ‍ॅरे लीटकोड सोल्यूशनमध्ये दोन घटकांचे जास्तीत जास्त उत्पादन शोधण्याचे जटिल विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन), एन = अ‍ॅरेचा आकार. साध्या तुलना ऑपरेशन्ससाठी आम्ही रेषीय पळवाट चालवितो.

जागेची जटिलता

ओ (1), स्थिर स्मृती वापरली म्हणून.