leetcode刷題之陣列NO.4

語言: CN / TW / HK

1.題目

給定一個數組 nums,編寫一個函式將所有 0 移動到陣列的末尾,同時保持非零元素的相對順序。

示例:

輸入: [0,1,0,3,12]

輸出: [1,3,12,0,0]

說明:

必須在原陣列上操作,不能拷貝額外的陣列。

儘量減少操作次數。

2.解法一:雙指標法

2.1.思路分析

當看到題目後,首先重構題意:

  • 未知量是什麼?未知量是將所有的0移動到末尾,且保持順序。
  • 條件是什麼?條件是一個數組,可以隨意訪問。
  • 約束是什麼?約束是空間複雜度為O(1)。
    重構完題目後,開始根據題目思考演算法:
  • 要將0移到末尾,還要保持順序,那麼一種辦法就是利用之前題目中的刪除指定元素,將0刪除,然後後面的元素全部填0。

2.2.程式碼實現

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int slow = 0;
        int fast = 0;

        while (fast < nums.size()) {
            if (nums[fast] != 0) {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        for (int i = slow; i < nums.size(); i++) {
            nums[i] = 0;
        }
    }
};

2.3.演算法分析

  • 該演算法的時間複雜度為O(n)。

3.總結

  • 演算法的本質就是窮舉,利用計算機的計算速度,從而求得結果,而非那些高深的公式,一下子就給出了答案,那是數學。
  • 在解題的時候,首先要自己思考,思考出來了,去看看有沒有比自己更好的辦法;沒有思考出來,去看看題解,看看自己錯在哪裡,沒有想出哪些部分以及為什麼。