LC283 - 移动零

package DoublePointers

func moveZeroes(nums []int) {
    moveZeroes2(nums)
}

// 时间复杂度: O(n^2), 空间复杂度: O(1)
func moveZeroes1(nums []int) {
    left, right := 0, len(nums)-1
    for left <= right {
        if nums[left] == 0 {
            moveToEnd(nums, left, right)
            right--
        } else {
            left++
        }
    }
}

func moveToEnd(nums []int, left int, right int) {
    tmp := nums[left]
    for i := left; i < right; i++ {
        nums[i] = nums[i+1]
    }
    nums[right] = tmp
}

// 时间复杂度: O(n), 空间复杂度: O(1)
func moveZeroes2(nums []int) {
    left, right := 0, 0
    for right < len(nums) {
        if nums[right] != 0 {
            nums[left], nums[right] = nums[right], nums[left]
            left++
        }
        right++
    }
}

moveZeroes1方法中，右侧指针维护零区，由于题目要求所有非零数值的相对位置保持不变，因此不能简单交换左右指针指向的数字，必须进行整体的挪动，时间复杂度为O(n^2)。

moveZeroes2方法中，左侧指针维护非零区，交换操作可以维持所有非零数值的相对位置保持不变，时间复杂度为O(n)。