題目

https://leetcode.com/problems/move-zeroes/

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Example:

Example:

Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

Note:

1. You must do this in-place without making a copy of the array.
2. Minimize the total number of operations.

解答

C#

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

結果

Runtime: 240 ms, faster than 100% of C# online submissions.

Memory Usage: 30.8 MB, less than 6.25% of C# online submissions.

Time Complexity: O(n)

Space Complextiy: O(1)

為什麼我要這樣做？

這題我覺得蠻有意思的，第一次把題目加進Favorite

需求是將把所有 0 都放在 Array 最後

1. 用一個 pointer 去記錄可以 swap 的第一個 0
2. 若遇到元素 nums[i] 不為 0 時
   • 判斷 pointer 及 i 是不是一樣
     • 如果 一樣 ，就不需要 swap (沒有自己在跟自己交換的)
     • 如果 不一樣，就需要 swap，把現在這個 int 跟 pointer上記住的 0 交換
   • pointer++ ，再找尋下一個需要交換的 0

示意圖

以上就是這次 LeetCode 刷題的分享啦！
如果其它人有更棒的想法及意見，請留言或寄信(t4730@yahoo.com.tw) 給我。
那我們就下回見囉