ایک صف لیٹ کوڈ حل میں دو عناصر کی زیادہ سے زیادہ مصنوعات


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے سیمسنگ
لڑی

مسئلہ "ایک صف میں دو عنصروں کی زیادہ سے زیادہ مصنوعات" میں ، ہمارا مقصد دو اشاریہ جات کو تلاش کرنا ہے 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 تلاش کرنے کے بجائے ، ہم کر سکتے ہیں ترتیب دیں la صف صعودی ترتیب میں اس سے یہ یقینی بنائے گا کہ دو سب سے بڑے عنصر آخر میں ہیں۔ لہذا ، مصنوعات (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. ہر عنصر کے لئے:
    • چیک کریں کہ آیا یہ پہلے میکس سے بڑا ہے:
      • اگر سچ ہے:
        • دوسرا میکس = پہلا میکس سیٹ کریں
        • پہلے میکس = موجودہ عنصر کو اپ ڈیٹ کریں
      • اور:
        • اگر یہ سیکنڈ میکس سے زیادہ ہے
          • سیکنڈ میکس = موجودہ عنصر کو اپ ڈیٹ کریں
  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 = سرنی کا سائز۔ ہم سادہ موازنہ کارروائیوں کے لئے ایک خطی لوپ چلاتے ہیں۔

خلائی پیچیدگی

O (1) ، چونکہ مستقل میموری استعمال ہوتی ہے۔