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

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Samsung
alqoritmlər Geyim kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutionsBaxılıb 83

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.

“Bir sıra iki elementdən maksimum məhsul” problemində məqsədimiz iki indeks tapmaqdır i 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.

misal

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

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

  1. Dizini sıralayın
  2. 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);
    }
}
20

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

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

Alqoritm

  1. İ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).
  2. Dizinin başlanğıcından sonuna qədər bir döngə işlədin.
  3. 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
  4. 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);
    }
}
20

Bir sıra Leetcode həllində iki elementdən maksimum məhsul tapmağın mürəkkəbliyi təhlili

Zamanın mürəkkəbliyi

O (N), N = Dizinin ölçüsü. Sadə müqayisə əməliyyatları üçün xətti bir döngə aparırıq.

Kosmik mürəkkəblik

O (1), kimi daimi yaddaş istifadə olunur.

Crack Sistemi Dizayn Müsahibələri
Translate »