תוצר מקסימלי של שני אלמנטים בפתרון Array Leetcode


רמת קושי קַל
נשאל לעתים קרובות סמסונג
מערך

בבעיה "מוצר מקסימלי של שני אלמנטים במערך", המטרה שלנו היא למצוא שני מדדים i ו j במערך נתון של מספרים שלמים a, כך שהמוצר (a [i] - 1) * (a [j] - 1) הוא מקסימלי. המערך כולל לפחות שני אלמנטים וכל האלמנטים חיוביים. הבעיה שהמוצר הנדרש מתאים לטווח המספרים השלמים. עלינו להדפיס את הערך של (a [i] - 2) * (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 המכילים את שני האלמנטים הגדולים ביותר, אנו יכולים sort מה היא מערך בסדר עולה. זה יוודא ששני האלמנטים הגדולים נמצאים בסוף. מכאן, המוצר (a [n - 1] - 1) * (a [n - 2] - 1) תהיה התוצאה הנדרשת.

אַלגוֹרִיתְם

  1. מיין את המערך
  2. הדפס את התוצאה: (a [n - 1] - 1) * (a [n - 2] - 1)

יישום אלגוריתם למציאת מוצר מקסימלי של שני אלמנטים במערך

תוכנית 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';
}

תוכנית Java

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), כאשר אנו משתמשים במרחב זיכרון קבוע.

גישה (אופטימלית)

כפי שדנו לעיל, עלינו למצוא את שני האלמנטים הגדולים במערך. על ידי מיון כל המערך, אנחנו לְהַגזִים העבודה הנדרשת. לכן, מיטבי למצוא את האלמנט הראשון והשני בגודלו במערך על ידי השוואת פעולות פשוטות. לפיכך, ניתן להשיג את התוצאה הנדרשת כ- (firstMax - 1) * (secondMax - 1).

תוצר מקסימלי של שני אלמנטים בפתרון Array Leetcode

אַלגוֹרִיתְם

  1. אתחל שני משתנים: firstMax ו- secondMax כאפס (כך שכל ערך במערך מעדכן אותם באופן מקומי).
  2. הפעל לולאה מתחילת המערך ועד סופו.
  3. לכל אלמנט:
    • בדוק אם הוא גדול מ- firstMax:
      • אם זה נכון:
        • הגדר secondMax = firstMax
        • עדכן firstMax = רכיב הנוכחי
      • אַחֵר:
        • אם הוא גדול משנימקס
          • עדכן את secondMax = רכיב הנוכחי
  4. הדפיס את התוצאה

יישום אלגוריתם למציאת מוצר מקסימלי של שני אלמנטים בפתרון Array Leetcode

תוכנית 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';
}

תוכנית Java

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

ניתוח מורכבות של מציאת מוצר מקסימלי של שני אלמנטים בפתרון מערך Leetcode

מורכבות זמן

O (N), N = גודל המערך. אנו מפעילים לולאה ליניארית לצורך פעולות השוואה פשוטות.

מורכבות חלל

O (1), כאשר משתמשים בזיכרון קבוע.