数组移零代码异常：非零元素顺序不符预期，求错误排查

需求：将数组中的所有零移至末尾，且保持非零元素的原有顺序。

现有代码：

class Solution {
    public void moveZeroes(int[] nums) {
       for (int i = 0; i < nums.length;i++) {
           if (nums[i]==0) {
               for(int j = i+1; j < nums.length;j++) {
                   if(nums[j]!=0) {
                       int temp = nums[i];
                       nums[i]=nums[j];
                       nums[j]=temp;
                   }
               }
           }
       } 
    }
}

输入[0,1,0,3,12]时，预期输出[1,3,12,0,0]，实际得到[12,3,1,0,0]，错误原因如下：

• 内层循环找到第一个非零元素交换后，没有终止内层循环，导致后续的非零元素会持续和当前i位置的元素交换。比如第一次i=0时，先和j=1的1交换，数组变成[1,0,0,3,12]，但内层循环继续执行，j走到3时又和i=0交换，数组变成[3,0,0,1,12]，j走到4时再次交换，最终完全打乱了非零元素的原有顺序。

修正代码（基于原有思路） #

只需要在交换后跳出内层循环，保证每次仅将当前零位置与第一个非零元素交换：

class Solution {
    public void moveZeroes(int[] nums) {
       for (int i = 0; i < nums.length;i++) {
           if (nums[i]==0) {
               for(int j = i+1; j < nums.length;j++) {
                   if(nums[j]!=0) {
                       int temp = nums[i];
                       nums[i]=nums[j];
                       nums[j]=temp;
                       // 找到第一个非零元素后立即终止内层循环
                       break;
                   }
               }
           }
       } 
    }
}

更高效的实现方案（快慢指针法） #

原有思路时间复杂度为O(n²)，用快慢指针可以将时间复杂度优化到O(n)，同时保持非零元素顺序：

class Solution {
    public void moveZeroes(int[] nums) {
        int slow = 0;
        // 快指针遍历数组，将非零元素依次放到慢指针位置
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != 0) {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        // 将慢指针之后的所有位置填充为0
        for (; slow < nums.length; slow++) {
            nums[slow] = 0;
        }
    }
}

内容的提问来源于stack exchange，提问作者riri