Sıfırları köçürün LeetCode Həlli

Problem bəyanat

Problem, Move Zeroes LeetCode Solution bildirir ki, sizə sıfır və sıfır elementləri olan massiv verilir və siz massivdəki sıfırdan fərqli elementlərin nisbi sırasını qoruyaraq bütün sıfırları massivin sonuna köçürməlisiniz. Bunun üçün siz də yerində alqoritm tətbiq etməlisiniz.

Pin

Nümunələr:

Test işi 1 –

Daxiletmə – [0, 1, 0, 3, 12]

Çıxış – [1, 3, 12, 0, 0]

Test işi 2 –

Giriş – [0]

Çıxış – [0]

Test işi 3 –

Daxiletmə – [10, 11, 0, 1, 2, 5]

Çıxış – [10, 11, 1, 2, 5, 0]

Yerli həll nədir?

Yerində o deməkdir ki, əlavə massiv üçün heç bir yer ayırmamalıyıq.

Hər halda, həll yolu hələ də çox asandır, çünki mövcud massivi dəyişdirməyə icazə verilir.

Yerində alqoritmin ən çox yayılmış nümunələrindən biri Heap Sort alqoritmidir.

Yanaşma

Fikir

Problem iki göstərici texnikasından istifadə etməklə həll edilə bilər. İki göstərici alacağıq, massivin başlanğıcına işarə edir. Sıfırla qarşılaşdığımız zaman göstəricilərdən birini digərini eyni yerdə saxlayaraq artırırıq. Sıfırdan fərqli elementlə qarşılaşdıqda, göstəricilərin yerində mövcud olan dəyərləri dəyişdiririk və hər ikisini artırırıq.

Move Zeroes LeetCode Həlli üçün kod

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size();
        int i = 0, j = 0;
        while(j<n){
            if(nums[j]==0) j++;
            else{
                swap(nums[i], nums[j]);
                i++;
                j++;
            }
        }
    }
};

class Solution {
    public void moveZeroes(int[] nums) {
        int n = nums.length;
        int i = 0, j = 0;
        while(j<n){
            if(nums[j]==0){
                j++;
            }
            else{
                int temp = nums[j];
                nums[j] = nums[i];
                nums[i] = temp;
                i++;
                j++;
            }
        }
    }
}

class Solution(object):
    def moveZeroes(self, nums):
        n = len(nums)
        i = 0
        j = 0
        while j<n:
            if nums[j] == 0:
                j = j+1
            else:
                temp = nums[i]
                nums[i] = nums[j]
                nums[j] = temp
                i = i+1
                j = j+1

Move Zeroes LeetCode Həlli üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

Biz massivi yalnız bir dəfə keçdiyimiz üçün alqoritm üçün zaman mürəkkəbliyi O(n)-dir.

Kosmik Mürəkkəblik

Biz heç bir köməkçi fəzadan istifadə etmədiyimiz üçün alqoritm üçün fəza mürəkkəbliyi O(1)-dir.

Referans: https://algodaily.com/lessons/using-the-two-pointer-technique