原地移动数组零元素至末尾并保持非零顺序的其他解法探讨

给定整数数组nums，需将所有0移动至数组末尾，同时保持非零元素的相对顺序。注意必须原地操作，不得复制数组。

示例 #

• 示例1：输入nums = [0,1,0,3,12]，输出[1,3,12,0,0]
• 示例2：输入nums = [0]，输出[0]

约束条件 #

• 1 <= nums.length <= 10⁴
• -2³¹ <= nums[i] <= 2³¹ - 1

我的解法 #

public class MoveZeros {
    public void moveZeroes(int[] nums) {

        List<Integer> li = new ArrayList<Integer>(nums.length);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                li.add(nums[i]);
            }
        }
        while (nums.length > li.size()) {
            li.add(0);
        }
        for (int i = 0; i < li.size(); i++)
            nums[i] = li.get(i);
    }

    public static void main(String[] args) {
        int num[] = { 0, 1, 0, 3, 12 };
        MoveZeros move = new MoveZeros();
        move.moveZeroes(num);
        System.out.println(Arrays.toString(num));
    }
}

其他解法 #

方法一：双指针（快慢指针）法 #

这种方法属于原地操作，空间复杂度为O(1)，时间复杂度O(n)，比原解法更节省内存。

思路：用慢指针标记非零元素应该放置的位置，快指针遍历数组。遇到非零元素时，将快指针的值赋值给慢指针位置，慢指针右移。遍历完成后，把慢指针之后的所有位置统一设为0。

public class MoveZeros {
    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 (int i = slow; i < nums.length; i++) {
            nums[i] = 0;
        }
    }

    public static void main(String[] args) {
        int num[] = { 0, 1, 0, 3, 12 };
        MoveZeros move = new MoveZeros();
        move.moveZeroes(num);
        System.out.println(Arrays.toString(num));
    }
}

方法二：交换式双指针法 #

同样是原地操作，只需一次遍历即可完成，效率更高。

思路：慢指针始终指向当前第一个未被处理的0的位置，快指针遍历数组时，每遇到非零元素就和慢指针位置的元素交换，之后慢指针右移。这样遍历结束后，所有0都会被移到数组末尾。

public class MoveZeros {
    public void moveZeroes(int[] nums) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != 0) {
                // 交换快慢指针指向的元素
                int temp = nums[slow];
                nums[slow] = nums[fast];
                nums[fast] = temp;
                slow++;
            }
        }
    }

    public static void main(String[] args) {
        int num[] = { 0, 1, 0, 3, 12 };
        MoveZeros move = new MoveZeros();
        move.moveZeroes(num);
        System.out.println(Arrays.toString(num));
    }
}

内容的提问来源于stack exchange，提问作者Amar kumar Nayak