एक Array Leetcode Solution में दो तत्वों का अधिकतम उत्पाद


कठिनाई स्तर आसान
में अक्सर पूछा सैमसंग
ऐरे

समस्या में "एक ऐरे में दो तत्वों का अधिकतम उत्पाद", हमारा लक्ष्य दो सूचकांकों को खोजना है i और j पूर्णांक की दी गई सारणी में a, ऐसा है कि उत्पाद (एक [i] - 1) * ([[जे] - 1) अधिकतम है। सरणी में कम से कम 2 तत्व हैं और सभी तत्व सकारात्मक हैं। समस्या जो आवश्यक उत्पाद पूर्णांक सीमा में फिट होती है। हमें इष्टतम के लिए ([i] - 1) * ([[j] - 1) का मान प्रिंट करने की आवश्यकता है i & j.

उदाहरण

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

व्याख्या

स्पष्ट रूप से, 6 और 5 सबसे बड़ी और दूसरी सबसे बड़ी संख्या हैं। तो, उत्पाद = (एक [i] - 1) * ([[जे] - १) = २०।

दृष्टिकोण (छंटनी)

उत्पाद: (एक [i] - १) * ([[जे] - १) अधिकतम होगा जब एक [i] और [a] दो सबसे बड़े तत्व होते हैं। दो सूचकांकों को खोजने के बजाय I और j जिसमें दो सबसे बड़े तत्व हैं, हम कर सकते हैं तरह la सरणी बढ़ते क्रम में। यह सुनिश्चित करेगा कि दो सबसे बड़े तत्व अंत में हैं। इसलिए, उत्पाद ([[एन - १] - १) * ([[एन - २] - १) आवश्यक परिणाम होगा।

कलन विधि

  1. सरणी को सॉर्ट करें
  2. परिणाम प्रिंट करें: ([[एन - १] - १) * ([[एन - २] - १)

एक ऐरे में दो तत्वों के अधिकतम उत्पाद को खोजने के लिए एल्गोरिथ्म का कार्यान्वयन

C ++ प्रोग्राम

#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), एन = सरणी का आकार। हम उस सरणी को सॉर्ट करते हैं जिसमें O (NlogN) समय लगता है।

अंतरिक्ष की जटिलता

ओ (1), जैसा कि हम निरंतर मेमोरी स्पेस का उपयोग करते हैं।

दृष्टिकोण (इष्टतम)

जैसा कि हमने ऊपर चर्चा की, हमें सरणी में दो सबसे बड़े तत्वों को खोजने की आवश्यकता है। पूरे एरे को क्रमबद्ध करके, हम अति आवश्यक कार्य। तो, यह सरल तुलनात्मक संचालन द्वारा सरणी में पहला और दूसरा सबसे बड़ा तत्व खोजने के लिए इष्टतम है। इसलिए, आवश्यक परिणाम के रूप में प्राप्त किया जा सकता है (फर्स्टमैक्स - 1) * (सेकंडमैक्स - 1).

एक Array Leetcode Solution में दो तत्वों का अधिकतम उत्पाद

कलन विधि

  1. पहले दो वैरिएबल: फर्स्टमैक्स और सेकंडमैक्स ज़ीरो के रूप में (ताकि एरे में कोई भी वैल्यू उन्हें अच्छी तरह से अपडेट कर दे)।
  2. सरणी के प्रारंभ से उसके अंत तक एक लूप चलाएँ।
  3. हर तत्व के लिए:
    • जांचें कि क्या यह फर्स्टमैक्स से अधिक है:
      • यदि सत्य हैं:
        • सैकेंड मेमेक्स = फ़र्स्टमैक्स सेट करें
        • फ़र्स्टमैक्स = करंट-एलिमेंट को अपडेट करें
      • अन्य:
        • यदि यह सेकंडमैक्स से अधिक है
          • अद्यतन दूसरी रचना = वर्तमान-तत्व
  4. परिणाम प्रिंट करें

ऐरे लेटेकोड सॉल्यूशन में दो तत्वों के अधिकतम उत्पाद को खोजने के लिए एल्गोरिथ्म का कार्यान्वयन

C ++ प्रोग्राम

#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), निरंतर मेमोरी का उपयोग किया जाता है।