أقصى ناتج لعنصرين في حل 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.

النهج (الفرز)

المنتج: (أ [i] - 1) * (أ [ي] - 1) سيكون الحد الأقصى عندما يكون [i] و [j] أكبر عنصرين في المصفوفة. بدلًا من إيجاد مؤشرين i و j يحتويان على أكبر عنصرين ، يمكننا ذلك sort ال مجموعة في ترتيب تصاعدي. سيضمن هذا وجود أكبر عنصرين في النهاية. ومن ثم المنتج (أ [ن - 1] - 1) * (أ [ن - 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';
}

برنامج جافا

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).

تعقيد الفضاء

يا (1)، حيث نستخدم مساحة ذاكرة ثابتة.

النهج (الأمثل)

كما ناقشنا أعلاه ، نحتاج إلى إيجاد أكبر عنصرين في المصفوفة. بفرز المصفوفة بأكملها ، نحن تطرف العمل المطلوب. لذلك ، من الأفضل العثور على العنصر الأول والثاني الأكبر في المصفوفة من خلال عمليات المقارنة البسيطة. وبالتالي ، يمكن الحصول على النتيجة المطلوبة كـ (firstMax - 1) * (secondMax - 1).

أقصى ناتج لعنصرين في حل Array Leetcode

خوارزمية

  1. قم بتهيئة متغيرين: firstMax و secondMax كصفر (بحيث تقوم أي قيمة في المصفوفة بتحديثهما مبدئيًا).
  2. قم بتشغيل حلقة من بداية المصفوفة حتى نهايتها.
  3. لكل عنصر:
    • تحقق مما إذا كانت أكبر من firstMax:
      • إذا كان هذا صحيحا:
        • تعيين secondMax = firstMax
        • تحديث firstMax = العنصر الحالي
      • آخر:
        • إذا كانت أكبر من secondMax
          • تحديث 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';
}

برنامج جافا

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

تحليل التعقيد لإيجاد المنتج الأقصى لعنصرين في حل Array Leetcode

تعقيد الوقت

O (N) ، N = حجم المصفوفة. نقوم بتشغيل حلقة خطية لعمليات مقارنة بسيطة.

تعقيد الفضاء

يا (1) ، كما يتم استخدام ذاكرة ثابتة.