題目描述:?
思路:
????????(雙指針) O(n)O(n)O(n)
????????給定一個數組 nums,要求我們將所有的 0 移動到數組的末尾,同時保持非零元素的相對順序。
????????如圖所示,數組nums = [0,1,0,3,12],移動完成后變成nums = [1,3,12,0,0] ,下面來講解雙指針的做法。
????????我們定義兩個指針,i指針和k指針,i指針用來遍歷整個nums數組,k指針用來放置nums數組元素。然后將非0元素按照原有的相對順序都放置到nums數組前面,剩下的位置都置為0。這樣我們就完成了0元素的移動,同時也保持了非0元素的相對順序。
具體過程如下:
- 定義兩個指針i和k,初始化i = 0,k = 0。
- i指針向后移動,遍整個nums數組,如果 nums[i] != 0,也就是說遇到了非0元素,此時我們就將nums[i]元素放置到nums[k]位置,同時k++后一位。
- 最后將k位置之后的元素都賦值為0。
實現細節:
遍歷數組可以使用for(int x : nums),這樣就少定義一個指針,代碼也顯得更加簡潔。
時間復雜度分析: O(n)O(n)O(n) ,nnn是數組的長度,每個位置只被遍歷一次。
時間復雜度分析: O(1)O(1)O(1) ,只需要常數的空間存放指針變量。
代碼:
class Solution {
public:void moveZeroes(vector<int>& nums) {int k = 0;for(int x : nums)if(x != 0) nums[k++] = x;while(k < nums.size()) nums[k++] = 0; }
};