Максимални производ два елемента у низу Леетцоде решења


Ниво тешкоће Лако
Често питани у самсунг
Ред

У проблему „Максимални умножак два елемента у низу“, наш циљ је да пронађемо два индекса i j у датом низу целих бројева a, такав да је производ (а [и] - 1) * (а [ј] - 1) максималан. Низ има најмање 2 елемента и сви елементи су позитивни. Проблем што се тражени производ уклапа у целобројни опсег. Морамо да испишемо вредност (а [и] - 1) * (а [ј] - 1) за оптимално i & j.

Пример

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

Објашњење

Јасно је да су 6 и 5 највећи и други по величини бројеви. Дакле, производ = (а [и] - 1) * (а [ј] - 1) = 20.

Приступ (сортирање)

Производ: (а [и] - 1) * (а [и] - 1) биће максимум када су а [и] и а [ј] два највећа елемента у низу. Уместо да пронађемо два индекса и и ј која садрже два највећа елемента, можемо врста la поредак растућим редоследом. Ово ће осигурати да су два највећа елемента на крају. Дакле, производ (а [н - 1] - 1) * (а [н - 2] - 1) биће тражени резултат.

Алгоритам

  1. Сортирај низ
  2. Одштампајте резултат: (а [н - 1] - 1) * (а [н - 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

Анализа сложености проналажења максималног производа двају елемената у низу

Сложеност времена

О (НлогН), Н = величина низа. Сортирамо низ за који је потребно О (НлогН) време.

Свемирска сложеност

О (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

Анализа сложености проналажења максималног производа два елемента у решењу матричног кода

Сложеност времена

О (Н), Н = Величина низа. Покрећемо линеарну петљу за једноставне операције упоређивања.

Свемирска сложеност

О (1), како се користи константна меморија.