LeetCode #283 Move Zeroes 移動零

英文原文如下

Given an integer array nums, move all 0‘s to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

中文翻譯

給予一個整數陣列 nums,將所有的零移到最後但要保持非零元素的相對位置。

請注意,你必須在原地操作陣列,不得複製它。

範例及題目限制

Follow up: Could you minimize the total number of operations done?

進一步: 你可以降低操作的總數嗎?


解題思路

在題目說明中,有說明要在原地操作

所以說不管是複製陣列或是用一個 list 來儲存非零元素,其實都是不合規的

在這裡我們使用的解法是用一個簡單的迴圈以及使用一個整數變數來儲存替換位置

要是不為0,就會將目前位置的元素與 Idx位置的元素互換

Idx在非0的狀況下會加 1,這代表當出現 0 的時候,指針(Idx) 就會被指到第一個出現的 0 身上

然後在下一次交換時,就會將這個 0 與 另一個非零元素互換,就實現了將 0 移到後面~

C# 解決方案

方案1

public class Solution {
    public void MoveZeroes(int[] nums) {
        int Idx = 0;
        for(int i=0; i<nums.Length; i++){
            if (nums[i] != 0)
            {
                var tmp = nums[Idx];
                nums[Idx] = nums[i];
                nums[i] = tmp;
                Idx++;
            }
        }
    }
}

時間複雜度: O(n)

⚠️然後這裡是我的第一次嘗試,獻醜了…

public class Solution {
    public void MoveZeroes(int[] nums) {
        int cnt = 0;
        int max = nums.Length;
        
        if(max!=1)
        {
            for(int i = 0; i<max;i++)
            {

                int now = nums[i];
                if(i == max-cnt)
                {
                    break;
                }
                
                if(now == 0)
                {
                    cnt+=1;
                    for(int j=i;j<max-1;j++)
                    {
                        nums[j] = nums[j+1];
                    }
                    nums[max-1] = 0;
                    if(nums[i] == 0)
                    {
                        i-=1;   
                    }
                }

            } 
        }
    }
}

用了兩個指針在原地操作,時間複雜度是 O(n2)

Java 解決方案

方案1

class Solution {
    public void moveZeroes(int[] nums) {
        int Idx = 0;
        for(int i=0; i<nums.length; i++){
            if (nums[i] != 0)
            {
                int tmp = nums[Idx];
                nums[Idx] = nums[i];
                nums[i] = tmp;
                Idx++;
            }
        }
    }
}

結論

會寫這一題其實是因為在整理網站數據時,看到有人查詢了 move zeros 這一題

想說我居然沒有滿足讀者的期望,趕緊來看一下哈哈!

大家如果有不懂的地方或是題目都可以私訊粉絲專頁或是留言在下面喔!

🧡如果這篇文章有幫上你的一點點忙,那是我的榮幸

🧡收藏文章或幫我點個廣告,那都是對我的支持

✅如有任何疑問,歡迎透過留言或messenger讓我知道 !

題目連結 : Move Zeroes – LeetCode

一些隨機的LeetCode文章

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *