欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Leetcode 283:Move Zeros

程序员文章站 2024-02-17 10:19:04
...

问题描述:

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.

把0都移到数组后面

限制条件:
1 <= nums.length <= 104
-2^31 <= nums[i] <= 2 ^31 - 1

思路:
用一个指针从前面遍历。遇到0就交换到末尾。末尾还有一个指针,永远指向一个非0元素。但这个思路被证实是错的,因为会破坏原序
思路更正:
可以设两个指针(slow,fast)都是从0开始,fast指针用从头到尾作遍历数组的指针。如果fast指向的不是0,就交换slow和fast,完事后两个指针均继续向前走;若fast指向的是0,slow作为定位指针不动,fast继续向前探索。

代码一遍通过:

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

时间复杂度: O(n)

相关标签: leetcode