LeetCode第283題：

github地址

有夢想的電信狗

前言

本文用C++實現 LeetCode 第283題

---

題目描述

題目鏈接：https://leetcode.cn/problems/move-zeroes/description/

---

題目與思路分析

目標分析：

1. 將數組中所有的0移動到數組的末尾，同時保持非零元素的相對位置
2. 不復制數組，即原地移除，意味著時間復雜度為O(n)，空間復雜度為O(1)
3. 直接對原數組進行操作

思路：雙指針

• cur：用于掃描元素，從待掃描元素的第一個開始，因此初始下標為0
• dest：指向數組中，已處理的區間中，最后一個非零元素的下標，初始時還未處理，**初始下標為-**1

操作：

• cur < nums.size()時，進入循環判斷

• nums[cur] == 0 時：當前位置為0，cur++，略過該位置的元素0，dest不變

• nums[cur] != 0 時： 由于dest為已處理的區間中，最后一個非零元素的下標，因此dest++后指向下一個位置，再將非零元素nums[cur]與nums[dest] 交換，再cur++

  • 即遇到非零元素：
    • ++dest
    • std::swap(nums[cur], nums[dest]);
    • ++cur

代碼實現

• 時間復雜度：O(n)
• 空間復雜度：O(1)

class Solution {
public:void moveZeroes(vector<int>& nums) {int cur = 0, dest = -1;while(cur < nums.size()){if(nums[cur] == 0){++cur;}else{++dest;std::swap(nums[cur], nums[dest]);++cur;}}}
};

算法代碼優化

• 利用前置和后置++的特性最終優化，但不推薦這么寫，因為算法的可讀性下降了

class Solution {
public:void moveZeroes(vector<int>& nums) {int cur = 0, dest = -1;while(cur < nums.size()){if(nums[cur] == 0)++cur;elsestd::swap(nums[cur++], nums[++dest]);}}
};

---

以上就是本文的所有內容了，如果覺得文章對你有幫助，歡迎 點贊?收藏 支持！如有疑問或建議，請在評論區留言交流，我們一起進步

分享到此結束啦
一鍵三連，好運連連！

你的每一次互動，都是對作者最大的鼓勵！

---

征程尚未結束，讓我們在廣闊的世界里繼續前行！ 🚀