目錄
文章前言
題目描述?
算法原理講解
忽略限制條件的解法
原理講解
?思路總結
?代碼展示
雙指針解法
原理講解
思路總結
?代碼展示
大總結
💫只有認知的突破💫才來帶來真正的成長💫編程技術的學習💫沒有捷徑💫一起加油💫
? ? ? ? ? ?🍁感謝各位的觀看🍁歡迎大家留言🍁咱們一起加油🍁努力成為更好的自己🍁
文章前言
為了提高自己的編程技術和能力，本博主開始要更新相關算法題的內容了。我會分類型的進行算法題的講解，由于博主是第一次真正意義上接觸系統的刷題訓練，作為一個小白，有不足或錯誤的地方，很愿意聽取在座各位大佬的批評和指教。廢話不多說，讓我們開啟刷算法題的旅行吧！
題目描述?
題目鏈接：移動零
如圖所示的要求：
給你一個數組，要求把這個數組的0元素，全部移動到數組的后面，非0元素全部移動到數組的前面，而且這些非0元素的相對順序保持不變。注意：不能新開辟一個數組，然后再把這新數組里面的元素拷貝到以前的數組中，這是不允許的，只能在原數組上進行操作。
算法原理講解
忽略限制條件的解法
本博主在一開始寫這個題目的時候，就沒有注意到限制條件——不允許開辟數組。雖然，這個解法能在Leetcode上能通過，但是不符合題目要求。我想把這個寫法也保留下來，它也算是一種思想，萬一在別的題目就合適呢！
原理講解
創建一個和原數組空間大小一樣的新數組，在這個新數組上，創建兩個“指針”，這里的指針不是真正的指針，就是通過下標訪問的變量。第一個指針begin_num指向數組的首元素，第二個指針end_num指向數組的最后一個元素，如圖所示(以示例1為例)：
然后再去遍歷原數組，遇到0元素，就存放在end_num，然后end_num再向前 -? - ，為存儲下一個0元素做準備，當遇到非0元素時，就存放在begin_num，然后begin_num向后走 + +，為下一個非0元素做準備，直到原數組遍歷完畢。如圖所示：
?思路總結
1.新建立和原數組一樣大的數組
2.創建兩個“指針”，分別指向新數組的頭和尾處的空間
3.依次遍歷原數組
? ? ? ? ? ? ? ? 3.1：遇到0元素，就插入end_num，然后end_num- -
? ? ? ? ? ? ? ? 3.2：遇到非0元素，就插入begin_num，然后begin_num++
4.原數組訪問完畢就結束
5.在把新數組排好序的元素賦值拷貝給原數組
?代碼展示
class Solution {
public:void moveZeroes(vector<int>& nums) {vector<int>num(nums.size(),1); //開辟一樣大小的新數組//創建兩個指針auto end_num=num.end()-1; //指向新數組的首元素auto begin_num=num.begin(); //指向新數組的尾元素for(auto&e:nums){if(e==0) //0元素插入end_num{*end_num=e;end_num--;}else //非0元素插入begin_num{*begin_num=e;begin_num++;}}nums=num; //把排好序的新數組賦值拷貝給原數組}
};雙指針解法
原理講解
我們解題時，所謂的雙指針并不是真正的指針，不是int*,char*……。而是指向數組的下標變量，比如，0，1，2……。所以大家不要感到害怕。
因為題目要求只能在原數組進行操作，所以我們就要摒棄開辟新數組的思想了。根據題目要求：非0元素全部在數組的左邊，0元素全部在數組的右邊。使用新的思想：數組劃分(數組分塊)的思想,這個數組被劃分為兩個區域，一塊是非0區域，另一塊是0區域，如圖所示：
這個時候，創建兩個指針，一個是cur，另一個是dst。cur指針的作用：它把數組分為已處理和待處理的兩個部分。dst指針的作用：它把已處理過的數組分為，左邊全是非0元素(保持相對順序)和右邊全是0元素的兩個部分。所以，這倆指針把數組分為3個部分。如圖所示：
所以數組被分為三個區間：[0,dst] , [dst+1,cur-1] , [cur,n-1]。[0,dst]全是非0元素，[dst+1,cur-1]全是0元素，[cur,n-1]待處理。其中，dst指向非0元素區間的最后一個非0元素。在遍歷數組的過程中，始終保持這三個區間的性質不變，就會達到題目要求。讓cur=0指向首元素位置，因為要起始遍歷數組。對于dst，要使它指向首元素的前一個位置，dst=-1。因為dst指向的是非0元素，在起始位置，是無法確定起始元素是否為非0元素，所以就把dst放在前面。如圖所示：
當cur指向的元素是0時，dst不動。當cur指向的元素非0時，dst++,然后cur和dst指向的元素進行交換，然后cur繼續往后走，直到遍歷完數組結束。
思路總結
1.cur=0指向首元素，dst=-1指向數組前面
2.cur指向的元素為0 , dst不動
3.cur指向的元素非0，dst++
? ? ? ? ? ? ? ? ?3.1:然后swap(dst元素，cur元素)
? ? ? ? ? ? ? ? ?3.2：cur++往后走
4.cur遍歷完數組結束
?代碼展示
class Solution {
public:void moveZeroes(vector<int>& nums) {for(int dst=-1,cur=0;cur<nums.size();cur++)if(nums[cur])swap(nums[++dst],nums[cur]);}
};大總結
根據本題目的敘述和要求，具有很明顯的數組劃分的特點，我們要進行合理的區間劃分，在遍歷數組的過程中，要保持各個區間的性質不變，才會有對的結局。這里要注意dst的起始位置。
