Array Leetcode Solution တွင် Element နှစ်ခုမှအများဆုံးထုတ်ကုန်


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် Samsung
အခင်းအကျင်း

“ Array အတွင်းရှိ Elements နှစ်ခု၏အများဆုံးထုတ်ကုန်” ပြproblemနာတွင်ကျွန်ုပ်တို့၏ရည်မှန်းချက်မှာညွှန်းကိန်းနှစ်ခုရှာရန်ဖြစ်သည် i နှင့် j ကိန်း၏ပေးထားသောခင်းကျင်း၌တည်၏ aထုတ်ကုန် (က [ဈ] - 1) * * (က [ည] - 1) ကြောင်းထိုကဲ့သို့သောအများဆုံး။ Array တွင်အနည်းဆုံး element ၂ ခုရှိပြီး element အားလုံးသည် positive ဖြစ်တယ်။ လိုအပ်သောထုတ်ကုန်သည်ကိန်းဂဏန်းပမာဏနှင့်ကိုက်ညီသောပြproblemနာဖြစ်သည်။ ကျွန်ုပ်တို့သည်အကောင်းဆုံးသောအတွက် (a [i] - 2) * (a [j] - 1) ၏တန်ဖိုးကို print ထုတ်ရန်လိုအပ်သည် i & j.

မာတိကာ

နမူနာ

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

ရှင်းလင်းချက်

ရှင်းနေသည်မှာ ၆ နှင့် ၅ သည်အကြီးဆုံးနှင့်ဒုတိယအကြီးဆုံးနံပါတ်များဖြစ်သည်။ ဒီတော့ထုတ်ကုန် = (က [ဈ] - 6) * (က [ည] - 5) = 1 ။

ချဉ်းကပ်မှု (Sorting)

ထုတ်ကုန်: (က [ဈ] - 1) * (က [ည] - 1) a [i] နှင့် [j] တို့သည်ခင်းကျင်းမှုတွင်အကြီးဆုံးဒြပ်စင်နှစ်ခုဖြစ်သည့်အခါအများဆုံးဖြစ်လိမ့်မည်။ အကြီးမြတ်ဆုံးဒြပ်စင်နှစ်ခုပါရှိသောညွှန်းကိန်းနှစ်ခုနှင့် i ကိုရှာမည့်အစား၊ ကျွန်ုပ်တို့လုပ်နိုင်သည် ကြမ္မာအခင်းအကျင်း တက်နိုင်ရန်အတွက်။ ဤအရာသည်အကြီးမားဆုံးဒြပ်စင်နှစ်ခုအဆုံးသတ်သွားစေရန်သေချာစေပါလိမ့်မည်။ ထို့ကြောင့်ထုတ်ကုန် (က [n - 1] - 1) * (က [n - 2] - 1) လိုအပ်တဲ့ရလဒ်ဖြစ်လိမ့်မည်။

algorithm

  1. ခင်းကျင်းမှုကိုစီပါ
  2. ရလဒ်ပုံနှိပ်ပါ: (က [n - 1] - 1) * (တစ် [n - 2] - 1)

Array တွင် Element နှစ်ခုမှအများဆုံးကုန်ပစ္စည်းကိုရှာရန် algorithm ကိုအကောင်အထည်ဖော်ခြင်း

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

ဒြပ်စင်နှစ်ခုမှအများဆုံးထုတ်ကုန်တစ်ခုကို Array တွင်ရှာဖွေခြင်း၏ရှုပ်ထွေးမှုအားသုံးသပ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (NlogN), N ကို = ခင်းကျင်း၏အရွယ်အစား။ O (NlogN) အချိန်ယူသောခင်းကျင်းမှုကိုကျွန်ုပ်တို့ခွဲဝေသည်။

အာကာသရှုပ်ထွေးမှု

အို (၁)ကျနော်တို့စဉ်ဆက်မပြတ်မှတ်ဉာဏ်အာကာသကိုသုံးပါအဖြစ်။

ချဉ်းကပ်မှု (အကောင်းဆုံး)

အထက်တွင်ဆွေးနွေးခဲ့သည့်အတိုင်းကျွန်ုပ်တို့သည် array ထဲ၌အကြီးမားဆုံးသောအချက်နှစ်ချက်ကိုရှာရန်လိုအပ်သည်။ Array တစ်ခုလုံးကိုစီခြင်းအားဖြင့်ကျွန်ုပ်တို့သည် အလွန်အကျွံ လိုအပ်သောအလုပ်။ ထို့ကြောင့်၊ ပထမနှင့်ဒုတိယအကြီးဆုံးသောဒြပ်စင်ကိုရိုးရှင်းသောနှိုင်းယှဉ်စစ်ဆင်ရေးများဖြင့်ရှာဖွေရန်အကောင်းဆုံးဖြစ်သည်။ ထို့ကြောင့်, လိုအပ်သောရလဒ်အဖြစ်ရရှိနိုင်ပါသည် (firstMax - 1) * (secondMax - 1).

Array Leetcode Solution တွင် Element နှစ်ခုမှအများဆုံးထုတ်ကုန်

algorithm

  1. variable နှစ်ခုကိုစတင်ပါ။ firstMax နှင့် secondMax သုညအနေနှင့် (array ထဲရှိမည်သည့်တန်ဖိုးသည်မဆို၎င်းတို့ကိုအထူးအဆန်းမွမ်းမံနိုင်သည်)
  2. array ၏အစအဆုံးမှအဆုံးအထိကွင်းဆက်တစ်ခု run ပါ။
  3. element တိုင်းအတွက်
    • firstMax ထက်ကြီးလားစစ်ဆေးပါ။
      • မှန်လျှင်:
        • secondMax = firstMax သတ်မှတ်မည်
        • updateMax = လက်ရှိဒြပ်စင်ကို Update လုပ်ပါ
      • ကျန် -
        • ဒါကြောင့် secondMax ထက်သာ။ ကြီးမြတ်လျှင်
          • updateMax = လက်ရှိ - ဒြပ်စင် update လုပ်ပါ
  4. ရလဒ်ပုံနှိပ်ပါ

Array Leetcode Solution တွင် Element နှစ်ခုမှအများဆုံးထုတ်ကုန်ကိုရှာဖွေရန် Algorithm ကိုအကောင်အထည်ဖော်ခြင်း

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

Array Leetcode Solution တွင် Element နှစ်ခုမှအများဆုံးထုတ်ကုန်ကိုရှာဖွေခြင်း၏ရှုပ်ထွေးမှုအားသုံးသပ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (N), N ကို = ခင်းကျင်း၏အရွယ်အစား။ ရိုးရှင်းသောနှိုင်းယှဉ်စစ်ဆင်ရေးများအတွက် linear ကွင်းဆက်ကိုအသုံးပြုသည်။

အာကာသရှုပ်ထွေးမှု

အို (၁)၊ စဉ်ဆက်မပြတ်မှတ်ဉာဏ်ကိုအသုံးပြုသည်အဖြစ်။