Leetcode 移动零

移动零

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

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

我的思路

双指针，首先删掉零，慢指针遇到零就停下，快指针遇到零就跳过，随后将快指针索引的值赋值给慢指针，当快指针移动至数组尾，将慢指针之后的元素全部赋值为0，解决问题。

代码

代码语言：javascript复制

func moveZeroes(nums []int)  {
    fastP, lowP := 0, 0
    for fastP < len(nums) {
        for fastP < len(nums) && nums[fastP] == 0 {
            fastP  
        }
        if fastP == len(nums) {
            break
        }
        nums[lowP] = nums[fastP]
        fastP  
        lowP  
    }
    for lowP < len(nums) {
        nums[lowP] = 0
        lowP  
    }
}

性能

代码语言：javascript复制

执行用时：32 ms, 在所有 Go 提交中击败了13.23%的用户
内存消耗：6.5 MB, 在所有 Go 提交中击败了18.44%的用户
通过测试用例：74 / 74

由于数组的每个位置都要进行赋值操作，因此性能较差。

题解

双指针，慢指针遇到元素是0则停下，快指针跳过所有0值，将快慢指针所指元素交换；继续往后遍历，重复上述过程，直到快指针走至数组尾。 由于大大减少了赋值次数，因此时间复杂度有较大提升。

代码语言：javascript复制

func moveZeroes(nums []int)  {
    fastP, lowP := 0, 0
    for fastP < len(nums) {
        if nums[lowP] ==0 {
            for fastP < len(nums) && nums[fastP] == 0 {
                fastP  
            }
            if fastP == len(nums) {
                break
            }
            nums[lowP], nums[fastP] = nums[fastP], nums[lowP]
        }
        fastP  
        lowP  
    }
}

性能:

代码语言：javascript复制

执行用时：20 ms, 在所有 Go 提交中击败了72.32%的用户
内存消耗：6.5 MB, 在所有 Go 提交中击败了18.44%的用户
通过测试用例：74 / 74

leetcode 内存 数组 性能 指针

0 人点赞