移動零

問題描述

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

請注意，必須在不復制數組的情況下原地對數組進行操作。

解決思路

為了將所有 0 移動到數組的末尾，我們可以使用雙指針方法，其中一個指針 j 用于記錄非零元素的位置，另一個指針 i 用于遍歷整個數組。

具體解決步驟如下：

1. 初始化指針 j 為 0。

2. 遍歷數組 nums 中的每個元素 nums[i]，其中 i 表示當前遍歷的位置。

3. 如果 nums[i] 不等于 0，將 nums[i] 的值賦給 nums[j]，然后將 j 自增 1，以維護 j 指針的位置。

4. 繼續(xù)遍歷數組直到結束。

5. 遍歷結束后，將從 j 開始的數組元素都設置為 0，以將所有 0 移動到末尾。

代碼實現

以下是使用Python編寫的代碼，實現了上述解決思路，并添加了注釋以解釋每個步驟：

class Solution:def moveZeroes(self, nums):if not nums:returnj = 0 for i in range(len(nums)):if nums[i] != 0:nums[j] = nums[i]j += 1for i in range(j, len(nums)):nums[i] = 0

時間復雜度分析

這個算法只需要遍歷一次數組，因此時間復雜度是 O(n)，其中 n 是數組的長度。

空間復雜度分析

這個算法只使用了常數額外空間，因此空間復雜度是 O(1)。

結論

移動零問題是一個簡單的數組操作問題，通過雙指針方法，我們可以在不復制數組的情況下原地將所有 0 移動到數組的末尾。這個算法的時間復雜度和空間復雜度都在合理范圍內，適用于大多數情況。希望這篇博客能夠幫助你更好地理解和解決移動零問題。