Self LeetCode Həllindən başqa massiv məhsulu

cuqquldamaq Facebook LinkedIn Bufer Reddit Tumblr

Mündəricat

Problem bəyanat

Özünü LeetCode Həllindən başqa massiv məhsulu – Tam ədəd massivi verilmişdir nums, qayıt bir sıra answer belə answer[i] -nin bütün elementlərinin hasilinə bərabərdir nums savayı nums[i].

İstənilən məhsul prefiks və ya şəkilçisi nums is zəmanətli sığmaq a 32-bit tam.

Siz daxil olan bir alqoritm yazmalısınız O(n) vaxt və bölmə əməliyyatından istifadə etmədən.

misal

Test işi 1:

Input:

ədədlər = [1, 2, 3, 4]

Çıxış:

[24, 12, 8, 6]

Test işi 2:

Input:

ədədlər = [-1, 1, 0, -3, 3]

Çıxış:

[0, 0, 9, 0, 0]

Izahat

Çıxış massivi hər bir elementin məhsuludur array həmin indeksdə mövcud olan rəqəm istisna olmaqla.

Yanaşma:

Məhdudiyyətlərə baxmazdan əvvəl gəlin problemi olduğu kimi həll etməyi düşünək.

İlk baxışdan aydın olur ki, biz bu problemi iki yoldan biri ilə asanlıqla həll edə bilərik:

Massivdəki hər bir elementin məhsulunu hesablayın nums. Sonra yaradın result ilə eyni uzunluqda massiv nums, nəticədə hər bir element üçün result[i] = product / nums[i]. Bu, çox sadədir və daxil olur O(n).

Bir yaradın result ilə eyni ölçülü massiv nums. Nəticələr massivini hesablaya bilərik:

<span class="hljs-keyword">for</span> (int i = <span class="hljs-number">0</span>; i < nums.length; i++) {
		results[i] = <span class="hljs-number">1</span>;
		<span class="hljs-keyword">for</span> (int j = <span class="hljs-number">0</span>; j < nums.length; j++) {
			<span class="hljs-keyword">if</span> (i != j) {
				result[i] *= nums[j];
			}
		}
}

İndi, bu ikinci cəhddə biz əslində nə edirik? Hər bir maddə üçün nums massivdə hər şeyin məhsulunu əldə etməyi bacarırıq nums ancaq o maddənin özü. Bunu bir az daha riyazi olaraq necə izah edə bilərik? Necə hesablayacağımızı müəyyən etməyə çalışaq results[i]:

<span class="hljs-function">For all i in the middle of <span class="hljs-title">nums</span> <span class="hljs-params">(i.e., not at either end)</span>:
    results[i] </span>= nums[<span class="hljs-number">0</span>] * ...... * nums[i-<span class="hljs-number">1</span>] * nums[i + <span class="hljs-number">1</span>] * ...... * nums[nums.length - <span class="hljs-number">1</span>]

For i = <span class="hljs-number">0</span>:
    results[i] = nums[i + <span class="hljs-number">1</span>] * ...... * nums[nums.length - <span class="hljs-number">1</span>]
		
For i = nums.length - <span class="hljs-number">1</span>:
    results[i] = nums[<span class="hljs-number">0</span>] * ...... * nums[i-<span class="hljs-number">1</span>]

Ümid edirəm ki, bu, bir az daha yaxşı ifadə edir. Əsasən, nəticələr əldə etmək üçün[i], hər hansı bir i üçün məhsulu ədədlərin[i] solunda və sağında hesablayırıq.. Bunu daha sonra yadda saxlayın!

Fərasət

Biz məhdudiyyətləri bilirik və bir həll yolu tapmalıyıq!

Sol və Sağ Məhsullar

Tutaq ki, bizdə tam ədədlər massivi var: [1, 2, 3, 4, 5, 6, 7, 8]. 4-dən başqa bütün maddələrin məhsulunu hesablayaq (indeks = 3)

1 * 2 * 3 * 5 * 6 * 7 * 8

biz bunu necə edərdik. Bu məhsul 4-ün solunda və sağında olan hər şeyin məhsuludur. Bu, aşağıdakıları etməyə bərabərdir:

(1 * 2 * 3) * (5 * 6 * 7 * 8)

Bu, sol məhsulun (soldakı hər şeyin məhsulu) və sağ məhsulun (sağdakı hər şeyin məhsulu) məhsuludur.
İndi ədədlərlə hər hansı i-ci bənd üçün biz ondan başqa hər şeyin məhsulunu onun sol və sağ məhsulunu vuraraq hesablaya bilməliyik!

Sol Məhsulları (və Sağ Məhsulları) tapmaq O(n)-da edilə bilər!

Sol məhsul massivini hesablamağa çalışaq, belə ki, üçün left[i] = bu misaldan istifadə edərək, ədədlərin[i] solunda olan hər şeyin məhsulu ([1,2,3,4]).

left[0] = 1 (Radların[0] solunda heç nə yoxdur, ona görə də onu 1-ə təyin etdik)
left[1] = 1 (1 ədədlərin [0] solundadır, ona görə də onu 1-ə təyin etdik)
left[2] = 1 * 2
left[3] = 1 * 2 * 3

Həmin məhsullardakı naxışı axtarın (Burada naxış var!)
left[1] = 1 = left[0] * 1 = left[0] * nums[0]
left[2] = 1 * 2 = left[1] * 2 = left[1] * nums[1]
left[3] = 1 * 2 * 3 = left[2] * 3 = left[2] * nums[2]

Nümunə: left[i] = left[i-1] * nums[i-1] !

Bənzər bir vəziyyəti düzgün məhsul massivi-> üçün göstərə bilərik right[i] = right[i+1] * nums[i+1]

right[3] = 1 (Radların[3] solunda heç nə yoxdur, ona görə də onu 1-ə təyin etdik)
right[2] = 4 (4 rəqəmlərin sağındadır[2])
right[1] = 4 * 3
right[0] = 4 * 3 * 2

Həmin məhsullardakı naxışı axtarın (Burada naxış var!)
right[2] = 4 = right[3] * 4 = right[3] * nums[3]
right[1] = 4 * 3 = right[2] * 3 = right[2] * nums[2]
right[0] = 4 * 3 * 2 = right[1] * 2 = right[1] * nums[1]

Həll

İndi biz sol məhsul massivinin və sağ məhsul massivinin necə hesablanacağını bildiyimiz üçün bunu sadəcə olaraq deyə bilərik results[i] = left[i] * right[i]!!

Özündən başqa massiv məhsulunun kodu

Java Proqramı

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] left = new int[nums.length];
        
        int[] right = new int[nums.length];
        
        left[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            left[i] = left[i-1] * nums[i-1];
        }
        
        right[nums.length - 1] = 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            right[i] = right[i+1] * nums[i+1];
        }
        
        int[] product = new int[nums.length];
        for (int i = 0; i < product.length; i++) {
            product[i] = left[i] * right[i];
        }
        
        return product;
    }
}

C ++ Proqramı

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n= nums.size();      
        vector<int> res(n);
        
        res[0] = nums[0];
        for(int i=1;i<n;i++){
            res[i] = res[i-1] * nums[i];
        }
      
        res[n-1] = res[n-2];
        int r=1;
        for(int i=n-1;i>0;i--){
            res[i] = res[i-1] * r;
            r *= nums[i];
        }
        res[0] = r;
       
        return res;
    }
};

Özünü LeetCode Həllindən başqa massiv məhsulu üçün mürəkkəblik təhlili

Zamanın mürəkkəbliyi: O (n)

Kosmik Mürəkkəblik: O (n)

cuqquldamaq Facebook LinkedIn Bufer Reddit Tumblr