Bir sıra Leetcode həllində iki elementdən maksimum məhsul -

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

cuqquldamaq Facebook LinkedIn Bufer Reddit Tumblr

“Bir sıra iki elementdən maksimum məhsul” problemində məqsədimiz iki indeks tapmaqdır i və j verilmiş tam bir sıra a, məhsul (a [i] - 1) * (a [j] - 1) maksimum olmalıdır. Dizinin ən azı 2 elementi var və bütün elementləri müsbətdir. Lazımi məhsulun tam aralığa uyğun olması problemi. Optimal üçün (a [i] - 1) * (a [j] - 1) dəyərini yazdırmalıyıq i & j.

Mündəricat

misal

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

Izahat

Aydındır ki, 6 və 5 ən böyük və ikinci ən böyük rəqəmlərdir. Beləliklə, məhsul = (a [i] - 1) * (a [j] - 1) = 20.

Yanaşma (çeşidləmə)

Məhsul: (a [i] - 1) * (a [j] - 1) a [i] və a [j] massivin iki ən böyük elementi olduqda maksimum olacaqdır. İki ən böyük elementi ehtiva edən iki i və j indekslərini tapmaq əvəzinə edə bilərik cür bu array artan qaydada. Bu, ən böyük iki elementin sonunda olmasını təmin edəcəkdir. Beləliklə, məhsul (a [n - 1] - 1) * (a [n - 2] - 1) tələb olunan nəticə olacaqdır.

Alqoritm

Dizini sıralayın
Nəticəni çap edin: (a [n - 1] - 1) * (a [n - 2] - 1)

Dizidəki İki Elementin Maksimum Məhsulunu tapmaq üçün alqoritmin tətbiqi

C ++ Proqramı

#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 Proqramı

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);
    }
}

Bir Dizidəki İki Elementin Maksimum Məhsulunun tapılmasının mürəkkəblik analizi

Zamanın mürəkkəbliyi

O (NlogN), N = massivin ölçüsü. O (NlogN) vaxtı alan serialı sıralayırıq.

Kosmik mürəkkəblik

O (1), daimi yaddaş məkanından istifadə etdiyimiz üçün.

Yanaşma (Optimal)

Yuxarıda müzakirə etdiyimiz kimi, massivdəki iki ən böyük elementi tapmalıyıq. Bütün massivi çeşidləyərək biz həddən artıq tələb olunan iş. Beləliklə, sadə müqayisə əməliyyatları ilə massivdəki birinci və ikinci ən böyük elementi tapmaq optimaldır. Beləliklə, tələb olunan nəticə olaraq əldə edilə bilər (firstMax - 1) * (secondMax - 1).

Alqoritm

İki dəyişəni başlanğıc halına gətirin: firstMax və secondMax sıfır olaraq (dizidəki hər hansı bir dəyər onları səmimi olaraq yeniləsin).
Dizinin başlanğıcından sonuna qədər bir döngə işlədin.
Hər element üçün:
- FirstMax-dan böyük olub olmadığını yoxlayın:
  - Doğrudursa:
    - SecondMax = firstMax seçin
    - FirstMax = cari elementi yeniləyin
  - Başqa:
    - SecondMax-dan böyükdürsə
      - SecondMax = cari elementi yeniləyin
Nəticəni çap edin

Bir sıra Leetcode həllində iki elementin maksimum məhsulunu tapmaq üçün alqoritmin tətbiqi

C ++ Proqramı

#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 Proqramı

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);
    }
}