Skip to content

Move Zeroes

题目

Given an integer array nums, move all 0‘s to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

Example 1:

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

Example 2:

Input: nums = [0]
Output: [0]

Constraints:

  • 1 <= nums.length <= 104
  • -231 <= nums[i] <= 231 - 1

Follow up: Could you minimize the total number of operations done?

思路

使用两个指针,一个指定layPos存放非0数值的位置,起始位置为0,另一个指定当前检查的位置checkPos;

如果checkPos当前的是非0数值,就将该数值填充到layPos,然后checkPos指针向右移动一个位置。layPos位置放置了非0数值后就向右移动1个位置。

最后checkPos超出数组后,不再检查。非0数值全部放置结束。此时layPos停在非0数值的下一个位置。

如果layPos没有超出数组,则将nums数组剩余位置都填充0

代码

java

class Solution {
    public void moveZeroes(int[] nums) {
        int layPos = 0;
        int checkPos = 0;
        while(checkPos < nums.length) {
            if (nums[checkPos] != 0) {
                nums[layPos] = nums[checkPos];
                layPos++;
            }
            checkPos ++;
        }
        while(layPos < nums.length) {
            nums[layPos++] = 0;
        }
    }
    
}
Published in数据结构和算法

Be First to Comment

Leave a Reply

Your email address will not be published.