题目描述

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

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1: 

1
2
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2: 

1
2
输入: nums = [0]
输出: [0]

提示 :

  • 1 <= nums.length <= 10^4
  • -2^31 <= nums[i] <= 2^31 - 1

进阶：你能尽量减少完成的操作次数吗？

解法

  • 双指针
    • 左右指针从0开始
    • 当遇到0时左右指针会岔开，左指针停下来维护数组最后一个元素
    • 右指针去遍历后边的元素，寻找合适的元素给左指针进行维护（交换）
    • left指针负责维护当前[0->left]数组的最后一个元素，保证不存在0
    • right指针负责遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public void moveZeroes(int[] nums) {
        int left=0,right=0;
        while (right<nums.length){
            if(nums[right]!=0){
               swap(nums, left, right);
               left++;
            }
            right++;
        }
    }
    public void swap(int[] num,int left,int right){
        int tmp=num[left];
        num[left]=num[right];
        num[right]=tmp;
    }
}
  • 时间复杂度：O(n)

来源：力扣（LeetCode）
链接：283. 移动零 - 力扣（LeetCode）