初级算法-数组-移动零

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

说明:
必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。

摘一个示例做个说明.
示例 1：
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

条件分析:

1. 保持非零相对位置 -> 不能更改数组非0顺序
2. 原数组操作
3. 尽量减少操作次数 -> 减少循环

解决思路1:

1. 根据分析1、2,说明需要在原数组中进行数据移动
2. 根据分析3,尽量减少循环次数

从后往前循环判断,如果为0,则删除该数据,并在数组末尾加0

解决思路2:

1.根据分析1、2,采用双指针,不是0的往前挪,

利用双指针,进行循环判断,不是0,则赋值到最前位置的指针,然后指针右移,最后循环指针后的内容置0

解决思路3:对思路2优化,做临时变量,然后交换

代码实现-Swift版本:

思路1代码:

func moveZeroes(_ nums: inout [Int]) {
    // 从后往前判断,如果有0,则挪到最后,并且删除该位置0
    for i in 0 ..< nums.count {
        if nums[nums.count - 1 - i] == 0 {
            nums.remove(at: nums.count - 1 - i)
            nums.append(0)
        }
    }
}

移动零 删除操作 提交结果.jpg

思路2代码:

func moveZeroes(_ nums: inout [Int]) {
    // 双指针,不是0的往前,然后剩下的全0
    var index = 0
    for i in 0 ..< nums.count {
        if nums[i] != 0 {
            nums[index] = nums[i]
            index += 1
        }
    }
    for i in index ..< nums.count {
        nums[i] = 0
    }
}

思路3代码:

func moveZeroes(_ nums: inout [Int]) {
    /**
     双指针,不是0的往前,然后剩下的全0
     时间36ms, 90.96% 内存14.1MB, 67.8%
     */
    var index = 0
    for i in 0 ..< nums.count {
        if nums[i] != 0 {
            let tmp = nums[index]
            nums[index] = nums[i]
            nums[i] = tmp
            index += 1
        }
    }
}

代码优化

func moveZeroes(_ nums: inout [Int]) {
    var index = 0
    for i in 0 ..< nums.count {
        if nums[i] != 0 {
            nums.swapAt(index, i)
            index += 1
        }
    }
}

移动零 双指针 提交结果.jpg

测试用例:

var array1 = [2,0,0,1,0,9,9]

考察要点:

• 数组
• 双指针