T283题目描述

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

解法一

思路

定义两个指针i，j，i用于遍历数组查找不是0的元素，j用于善后，将i找到的元素覆盖原先的数组，当i已经到达数组末尾时，j指向了最后一个填充非0元素的位置，从j+1开始，一直到数组末尾，填充0

代码

//方法体
public void moveZeroes(int[] nums) {
        
        int j=0;
        for(int i=0;i<nums.length;i++){
            if(nums[i] != 0){
                nums[j] = nums[i];
                j++;
            }
        }
        //注意：跳出循环时，j已经在最后一个非0元素下标的基础上，加了一个1，所以，直接从j开始用0覆盖
        for(int i=j;i<nums.length;i++){
            nums[i] = 0;
        }
        for (int num : nums) {
            System.out.println(num);
        }
    }

解法二

思路

定义两个指针i,j，i用于寻找非0，j用于定位0，等待0这个坑填好后才继续往后走，具体解释看代码

代码

public void moveZeroes(int[] nums) {

        int j=0;
        for(int i=0;i<nums.length;i++){
            /*
            j专门用于指向0,而i专门用于找非0
            下列注释掉的代码为分步骤执行的代码
             */
            //都不为0则都继续往后走
//            if(nums[i]!=0 && nums[j]!=0){
//                j++;
//            }
            //都为0，则j停下来，等i往后走找到非0，这样就可以填补这个坑了，填完后j也可以往后走了
//            else if(nums[i]==0 && nums[j]==0){
//                continue;
//            }
            //j还在0这停留，此时i传来了好消息，它找到了非0，可以开始替换啦，然后j继续往前走
//            else if (nums[i]!=0 && nums[j]==0){
//                int temp = nums[i];
//                nums[i] = 0;
//                nums[j] = temp;
//                j++;
//            }
            //如果nums[i]=0 此时j指向的就是0,也就是有0的地方就有j
            // j一定是等到他指向的元素不是0后才会继续往后走
            // 所以不存在nums[i]为0而nums[j]不为0的情况
            
            //简写代码
            if(nums[i]!=0){
                if(nums[j]==0){
                    int temp = nums[i];
                    nums[i] = 0;
                    nums[j] = temp;
                }
                j++;
            }
        }
        for (int num : nums) {
            System.out.println(num);
        }
    }

解题收获

错误点

• 一开始我是想将各个0的下标记录下来，之后利用这些下标对数组进行分段，每一段分别向前移动不同的位数（前面有几个0就移动几位），发现这样不现实，因为在移动的过程中数组是变化的，这样之前记录的下标就不稳定了，导致过程很复杂，最后也没有将思路实现，这很可惜。
• 后来我的想法是碰到一个0就往前移动，移动后指针指向的元素就不是0了，若是继续向后遍历，势必会出错，也意味着一个指针做不到，使用for循环会很麻烦。

疑惑点

解法二提到借用了快速排序的思想，但我很懵…，需要再将快速排序的算法看一遍

原大佬的解释如下：

这里参考了快速排序的思想，快速排序首先要确定一个待分割的元素做中间点x，然后把所有小于等于x的元素放到x的左边，大于x的元素放到其右边。
这里我们可以用0当做这个中间点，把不等于0(注意题目没说不能有负数)的放到中间点的左边，等于0的放到其右边。
这的中间点就是0本身，所以实现起来比快速排序简单很多，我们使用两个指针i和j，只要nums[i]!=0，我们就交换nums[i]和nums[j]

等我将快排理解完后再回来看这句话~