Üç Nömrənin Maksimum Məhsulu LeetCode Həll

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon alma ByteDance Citadel Facebook google Intuit microsoft Salesforce Boşalmaq Über
RedfinBaxılıb 21

Problem bəyanat

Üç Rəqəmin Maksimum Məhsulu LeetCode Həlli – Bizə massiv verilir, sual bizdən hər hansı 3 ədədin maksimum məhsulunu hesablamağı xahiş edir.

Nümunələr

Misal 1:

Input: nums = [1,2,3]
Output: 6

Misal 2:
Input: nums = [1,2,3,4]
Output: 24

Misal 3:
Input: nums = [-1,-2,-3]
Output: -6

Yanaşma

Bütün ədədlər 0-dan böyükdürsə, o zaman maksimum məhsul 3 ədədin ən böyük 3 ədədinin hasili olacağı aydındır. Problem mənfi ədədlər halında yaranır.

Gəlin əvvəlcə bəzi halları müşahidə edək, sonra isə həlli üzərində düşünək. Bu hallar üçün ədədlərin azalmayan qaydada çeşidləndiyini fərz edək.

Case 1:

ədədlər = [2, 3, 4, 7, 9, 100]

çıxış = 7 *9 *100

İzahat: Maksimum 3 ədəd 100, 9 və 7-dir

Case 2:

ədədlər = [-13, -12, -1, 0, 1, 3, 14, 16, 17]

çıxış = 14 *16 *17

İzahat: Maksimum 3 ədəd 17, 16 və 14-dir

Case 3:

ədədlər = [-13, -12, -11, -1, 0, 2, 3, 4, 5]

çıxış = -13*(-12)*5

İzahat: maksimum rəqəmlər 3, 4 və 5 olsa da, iki mənfi ədəddən daha böyük müsbət məhsul yarada bilərik, bu halda (-13)(-12) > 4 *5. 2 mənfi ədədi daxil etdikdən sonra heç bir mənfi ədədi daxil edə bilmərik, çünki bu, hasili mənfi, dolayısı ilə kiçik edəcək. Buna görə də 3-cü ədədi yalnız ən böyük müsbət kimi daxil etməliyik.

Sıralanmış massivdə maksimum məhsul ya son üç ən böyük element, ya da sonuncu (ən böyük) elementə vurulan ilk iki (mənfi element) olacaqdır.

Kodu

Üç Rəqəmin Maksimum Məhsulu üçün C++ kodu

class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        if(nums[n-1] <= 0) {
            return nums[n-1]*nums[n-2]*nums[n-3];
        }
        
        int res = nums[n-1];
        if(nums[0]*nums[1] >= nums[n-2]*nums[n-3]) {
            res *= nums[0]*nums[1];
        }
        else {
            res *= nums[n-2]*nums[n-3];
        }
        return res;
    }
};

Üç Rəqəmin Maksimum Məhsulu üçün Java kodu

public class Solution {
    public int maximumProduct(int[] nums) {
        Arrays.sort(nums);
        int option1 = nums[0] * nums[1] * nums[nums.length - 1];
        int option2 = nums[nums.length - 1] * nums[nums.length - 2] * nums[nums.length - 3];
        return Math.max(option1, option2);
    }
}

Üç Nömrənin Maksimum Məhsulu üçün Mürəkkəblik Təhlili LeetCode Həlli

Referans: https://en.wikipedia.org/wiki/Array_data_structure

Şərh yaz

Translate »