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

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon American Express alma Asana Bloomberg Citadel eBay Expedia Facebook Goldman Sachs google Intel JPMorgan LinkedIn lyft MakeMyTrip microsoft Nutanix Nvidia Kahin PayPal SAP XidmətNow cuqquldamaq Über VMware Yahoo Yandex
Groupon Walmart Qlobal texnologiyaBaxılıb 19

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.

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

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:

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

Translate »