双指针

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++;

            }

        }

    }

}