雙指針

4.移動零

二刷昨天的題，學習了新的數據結構StringBuilder。專為頻繁字符串拼接設計的可變字符串類。

(https://blog.csdn.net/m0_73941339/article/details/145651287)

二刷完昨天的題目，做到這題腦子已經轉不動了。做雙指針，一般雙指針初始時候都是在最左邊和最右邊，要先確定好左指針和右指針的具體起始位置（就是為什么指向這里，指向的什么？有規律是最好的——標記的是什么）(左指針在右指針的左邊)。不要輕易定下指針移動規則（要思考好怎么移動才是正確的）。雙指針交換或者移動的核心邏輯很重要。

這里：左指針指向非零，表示處理完了，可以向右移動；右指針指向零，表示處理完了，可以左移。

有的視頻提到是用快速排序的思想，那么先復習一下快速排序。

快速排序：

基本思想：通過篩選一個基準元素，將待排序列分割成兩個子序列，使其中一個子序列所有元素小于等于基準元素，另一個子序列的所有元素都大于基準元素。然后再對這兩個子序列分別進行快速排序，直到整個序列有序。

總結：我一開始的思路就是錯的：專注于把0移到末尾，而不是考慮將非零元素移到前面。當思路和代碼都不work的時候，應該換一種想法。多冷靜，想想問題的本質。

方法1（來自豆包）：

需要兩個指針，一個指針記錄非零元素的擺放位置（顯然是從0開始擺放），另一個指針遍歷數組，用于標記（找到）零和非零元素。對于找到的非零元素，根據指針設定的擺放位置進行擺放。最后讓指針所指向的擺放位置以及之后的位置都置為0即可。

方法1：

代碼：

class Solution {

??? public void moveZeroes(int[] nums) {

??????? int idx=0;

??????? while(idx<nums.length && nums[idx]!=0) idx++;

??????? for(int r = idx;r<nums.length;r++){

??????????? if(nums[r]!=0){

??????????????? nums[idx] = nums[r];

??????????????? idx++;

??????????? }

??????? }

??????? for(int i=idx;i<nums.length;i++) nums[i]=0;

??? }

}

注意，出現指針移動，一定要先寫數組越界的判斷。速度竟然超越了100%。第一次遇到紀念一下。

方法2（常見的題解）：

核心思想就是：將非零元素向前移動。每次交換都是用非零元素替換零元素，零元素會被逐步推導數組末尾。

這樣好想：假設已經有一段處理好的序列（符合題意），又來了一段序列要和前一段序列拼接，經過處理之后的到符合題意的總序列。那么這時候只需要把后一段序列中的非零元素與前一段序列中的零元素（這個零元素的開始位置應當是第一個零元素）互換位置即可。

class Solution {

? ? public void moveZeroes(int[] nums) {

? ? ? ? int l = 0;

? ? ? ? while(l<nums.length && nums[l]!=0) l++;

? ? ? ? for(int r = l; r < nums.length; r++){

? ? ? ? ? ? if(nums[r]!=0){

? ? ? ? ? ? ? ? nums[l]=nums[r];

? ? ? ? ? ? ? ? nums[r]=0;

? ? ? ? ? ? ? ? l++;

? ? ? ? ? ? }

? ? ? ? }

? ? }

}

對應官方題解的代碼，也是100%速度。（如果沒有出現0元素，那么左右指針元素的交換就不影響結果，相當于沒交換）

核心思想是：非零元素與最左側的零元素互換位置。

class Solution {

? ? public void moveZeroes(int[] nums) {

? ? ? ? int l = 0;

? ? ? ? for(int r = 0; r < nums.length; r++){

? ? ? ? ? ? if(nums[r]!=0){

? ? ? ? ? ? ? ? int temp=nums[l];

? ? ? ? ? ? ? ? nums[l]=nums[r];

? ? ? ? ? ? ? ? nums[r]=temp;

? ? ? ? ? ? ? ? l++;

? ? ? ? ? ? }

? ? ? ? }

? ? }

}