LeetCode-MoveZeroes

發表於 更新於 分類於 閱讀次數： Disqus：

原始題目

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.

中文翻譯

今天團隊大神又帶萌新刷 LeetCode 了，原始題目是 LeetCode 的 Move Zeroes，但是為了挑戰性，加了一點限制

  1. 將數字陣列裡所有 0 的元素移到最後面
  2. 不改變其他數字的排序
  3. 直接在該陣列物件完成操作,不可複製或建立新的陣列

TestCase:

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

解題

第一個版本

第一個版本就真的像是候捷說的全憑本能程序員，這個版本還算簡單，但進步空間還是很大的，套用了兩次迴圈，複雜度數值應該不會很好看

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public void MoveZeroes(int[] nums)
{
    for (var i = 0; i < nums.Length; i++)
    {
        // 如果已經是最後一格，不動作
        if (i == nums.Length - 1) continue;

        // 當前有數值，不動作
        if (nums[i] != 0) continue;

        // 找出下一個不是0的index
        var notZeroIndex = FindNotZero(nums, i);
        if (notZeroIndex == -1) continue; // 找不到，不動作

        // 交換數字
        nums[i] = nums[notZeroIndex];
        nums[notZeroIndex] = 0;
    }
}

private int FindNotZero(int[] nums, int currentIndex)
{
    for (var i = currentIndex; i < nums.Length; i++)
        if (nums[i] != 0) return i;
    return -1;
}

第二個版本

這個版本開始採用了兩個指標，所以變得有點難以理解，最後還是依靠大神提點才搞出了這個版本，原本以為應該是不錯了，但是實際上跑出來的數值，感覺跟第一個版本沒啥明顯差異

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public void MoveZeroes(int[] nums)
{
    var i = 0;
    var j = 1;
    while (j < nums.Length)
    {
        // 如果前面的為0，後面不為0，就交換
        if (nums[i] == 0 && nums[j] != 0)
        {
            nums[i] = nums[j];
            nums[j] = 0;
        }
        // 如果兩者都為0，那後面的 + 1
        else if (nums[i] == 0 && nums[j] == 0)
        {
            j++;
        }
        // 否則往下一個數字開始處理
        else
        {
            i++;
            j = i + 1;
        }
    }
}

第三個版本

最終由大神說明最終版本的思路，一樣是採用兩個指標，指標 right 用來順序跑回圈往下走；指標 left 就是用來交換數值用的

  1. left 指標都必須指在 0 上面等著被交換
  2. right 指標只有在不是 0 的時候才做交換
1
2
3
4
5
6
7
8
9
10
11
12
13
public void MoveZeroes(int[] nums)
{
    for (int left = 0, right = 0; right < nums.Length; right++)
    {
        if (nums[right] != 0)
        {
            int temp = nums[right];
            nums[right] = nums[left];
            nums[left] = temp;
            left++;
        }
    }
}


程式碼很簡短，速度也很快，第三種版本有一種豁然開朗的感覺，但是一開始就算知道思路，還是卡關很久，附上三個案例的步驟

陣列中沒有 0，在每一個步驟，left 實際上都是自己跟自己交換，然後最終 left 指標再+1

在步驟 3 的時候，right 碰到了 0，所以跳過不做事情；所以 left 也就被固定下來 (只有 right 碰到不是 0 的時候，left 才會增加)