问题描述

LeetCode 283 - Move Zeroes 要求我们将数组中的所有0移动到数组的末尾，同时保持非零元素的相对顺序。

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

示例：

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

要求：

1. 必须在原数组上操作，不能创建新数组
2. 尽量减少操作次数

解法一：寻找非零元素交换

这种解法的基本思路是从前往后遍历数组，当遇到0时，向后寻找第一个非零元素与之交换。

class Solution {
    public void moveZeroes(int[] nums) {
        int n = nums.length;
        for(int i = 0; i < n ; i++){
            if(nums[i] == 0){
                int j = i+1;
                while( j < n && nums[j] == 0){
                    j++;
                }
                if(j < n){
                    nums[i] = nums[j];
                    nums[j] = 0;
                }else{
                    break;
                }
            }
        }
    }
}

解法一分析

1. 算法思路：
   • 遍历数组，当找到一个0时，向后寻找第一个非零元素
   • 找到非零元素后，将其与当前位置的0交换
   • 如果找不到非零元素，说明后面全是0，直接结束
2. 时间复杂度分析：
   • 最坏情况下，数组开头有很多0，每次找到0时都需要遍历到数组末尾寻找非零元素
   • 时间复杂度为O(n²)，其中n是数组长度
3. 空间复杂度分析：
   • 只使用了几个变量，空间复杂度为O(1)

解法二：双指针法（填充法）

这种解法使用双指针技术，先将所有非零元素移到数组前面，然后将剩余位置填充为0。

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

解法二分析

1. 算法思路：
   • 使用slow指针记录非零元素应该放置的位置
   • fast指针遍历整个数组，当遇到非零元素时，将其放到slow指针位置，slow指针前进一步
   • 遍历结束后，将slow指针后的所有元素设为0
2. 时间复杂度分析：
   • 数组只被遍历两次，第一次找出所有非零元素，第二次填充0
   • 时间复杂度为O(n)，其中n是数组长度
3. 空间复杂度分析：
   • 只使用了几个变量，空间复杂度为O(1)

解法三：双指针法（交换法）

这种解法也使用双指针技术，但不是先填充非零元素再填充零，而是直接交换元素。

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

解法三分析

1. 算法思路：
   • 使用slow指针记录下一个非零元素应该放置的位置
   • fast指针遍历整个数组，当遇到非零元素时，将其与slow指针位置的元素交换，slow指针前进一步
   • 优化：当slow和fast指针指向同一位置时，避免不必要的交换操作
2. 时间复杂度分析：
   • 数组只被遍历一次，时间复杂度为O(n)，其中n是数组长度
3. 空间复杂度分析：
   • 只使用了几个变量，空间复杂度为O(1)

三种解法比较

解法优劣分析：

1. 解法一：
   • 优点：实现简单，容易理解
   • 缺点：时间复杂度高，在最坏情况下效率很低
   • 适用场景：数组较小或0较少且分布均匀的情况
2. 解法二：
   • 优点：时间复杂度低，稳定的O(n)性能
   • 缺点：可能进行不必要的写操作，尤其是当数组中0很少时
   • 适用场景：一般情况下都适用，特别是不关心写操作次数时
3. 解法三：
   • 优点：时间复杂度低，且写操作次数最少
   • 缺点：代码略微复杂一点
   • 适用场景：对写操作敏感的环境，如某些硬件设备的内存操作

总结

在解决LeetCode 283题目时，三种解法各有特点：

1. 解法一虽然直观但效率低下，时间复杂度为O(n²)
2. 解法二和解法三都采用双指针技术，时间复杂度降为O(n)
3. 解法三通过减少不必要的交换操作，进一步优化了解法二

从实际应用角度来看，解法三是最优选择，因为它不仅时间复杂度低，而且写操作次数最少。这种”双指针交换法”也是解决类似数组元素移动问题的常用技巧。