Sorted Array LeetCode Həllini birləşdirin

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.

Problem bəyanat

Sorted Array LeetCode Həllini birləşdirin – Sizə iki tam massiv verilir nums1 və nums2, sıralanır azalmayan sifariş, və iki tam ədəd m və n, içərisindəki elementlərin sayını təmsil edir nums1 və nums2 müvafiq.

Qatışmaq nums1 və nums2 sıralanmış tək massivdə azalmayan sifariş.

Son çeşidlənmiş massiv funksiya tərəfindən qaytarılmamalı, əksinə olmalıdır massiv daxilində saxlanılır nums1. Bunu təmin etmək üçün, nums1 uzunluğuna malikdir m + n, ilk harada m elementlər birləşdirilməli olan elementləri və sonuncunu bildirir n elementləri təyin olunur 0 və nəzərə alınmamalıdır. nums2 uzunluğuna malikdir n.

misal

Test işi 1:

Input:

ədəd1 = [1, 2, 3, 0, 0, 0]

m = 3

ədəd2 = [2, 5, 6]

n = 3

Çıxış:

[1, 2, 2, 3, 5, 6]

Izahat

Birləşdirdiyimiz massivlər [1,2,3] və [2,5,6]-dır. Birləşmənin nəticəsi [1,2,2,3,5,6] ədədlər1-dən gələn altı çizili elementlərlə əldə edilir.

Yanaşma:

Həll 01

• Əvvəldən 0 ədədini təkrarlamaq üçün j=2 götürdük.
• Bildiyimiz kimi nums1 m+n ölçüsünə malikdir və son massivdə yalnız ilk m elementləri olmalıdır.
• Beləliklə, biz m indeksinin bütün elementlərini nums2-nin bütün elementləri ilə əvəz edirik.
• Nəhayət, son çeşidlənmiş massivi əldə etmək üçün nums1 massivini çeşidləyəcəyik.
• Zamanın mürəkkəbliyi: O(nlogn) //çünki çeşidləmə nlogn vaxtını alır.

Həll 02

• Həll 01 ilə eyni məntiq, Ancaq burada istifadə etdik ölçüsünü dəyişdirin ().
• Resize() sadəcə elementləri muns1 massivində m indeksinə qədər saxlayacaq.
• Sonra insert() funksiyasından istifadə edərək nums2 massivinin bütün elementlərini daxil edəcəyik.
• Nəhayət, son çeşidlənmiş massivi əldə etmək üçün nums1 massivini çeşidləyəcəyik.
• Zamanın mürəkkəbliyi: O(nlogn) //çünki çeşidləmə nlogn vaxtını alır.

Həll 03

• Hər iki həll 01 və 02 O(nlogn) qəbul etdiyinə görə indi biz onu O(n+m) ilə həll etməyə çalışırıq.
• Biz tərs çeşidləmə metodundan istifadə edəcəyik.
• Biz 3 dəyişən götürdük: i (son massivdə təqdim olunacaq nums1-in son etibarlı elementi), j (nömrələrin2-nin sonuncu elementi) & k (nömrələrin1-in son indeksi)
• Birincisi, döngə zamanı ədəd1 və ədəd2-ni müqayisə edəcək və daha böyük element ədəd1[k]-də olacaq.
• Döngə bitdikdən sonra massivdə hələ də hər hansı element qalırsa, onlar növbəti 2-yə əlavə olunacaqlar döngə zamanı.
• Zamanın mürəkkəbliyi: O(m+n).

Pin

Sıralanmış massivlərin birləşmə kodu

Python proqramı

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        i, j, cur = m - 1, n - 1, m + n - 1
        
        while j > -1:
            if i > -1 and nums1[i] >= nums2[j]:
                nums1[cur] = nums1[i]
                i -= 1
            else:
                nums1[cur] = nums2[j]
                j -= 1
            
            cur -= 1

Java Proqramı

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int last1 = m-1;
        int last2 = n-1;
        
        int index = nums1.length-1;
        
        while (last1 >=0 && last2>=0) {
            int l = nums1[last1];
            int r = nums2[last2];
            
            if (l < r) {
                nums1[index--] = r;
                last2--;
            } else {
                nums1[index--] = l;
                last1--;
            }
        }
        
        while (last2 >=0) {
            int r = nums2[last2];
            
            nums1[index--] = r;
            last2--;
        }
    }
}

Birləşmə çeşidlənmiş massiv LeetCode Həlli üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi: O (m + n) burada m və n müvafiq olaraq nums1 və nums2-də sıfırdan fərqli elementlərin sayıdır, çünki biz onları birləşdirmək üçün hər iki massiv üzərində təkrar edirik.

Kosmik Mürəkkəblik: O (1) çünki biz birləşməni edirik yerində.