LeetCode高薪算法+计算机职称考试Swift in LeetCode

LeetCode 283. 移动零 Move Zeroes

2019-08-06  本文已影响1人  1江春水

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

【示例】

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

【说明】

1、必须在原数组上操作,不能拷贝额外的数组。
2、尽量减少操作次数。

【思路1】
1、把不为0的数字往前移,标记0的个数k,在后边添加k个0;
2、时间复杂度O(n)
3、空间复杂度O(1)

Swift代码实现

func moveZeroes(_ nums: inout [Int]) {
    var k = 0
    for i in 0..<nums.count {//先把不为0的数字提到前边
        if nums[i] != 0 {
            nums[k] = nums[i]
            k+=1
        }
    }
    for j in k..<nums.count {//后边补0
        nums[j] = 0
    }
}

【思路2】
1、使用一个指针变量来标记第一个0的index,遇到不为0的数字和0交换,直到交换完毕
2、时间复杂度O(n)
3、空间复杂度O(1)
4、很巧妙的!!!

Swift代码实现:

func moveZeroes(_ nums: inout [Int]) {
    var k = 0//永远标识第一个0的位置,当非0位置 和 0位置交换后,k++
    for i in 0..<nums.count {
        if nums[i] != 0 {
            if i != k {
                let tmp = nums[i]
                nums[i] = nums[k]
                nums[k] = tmp
            }
            k+=1
        }
    }
}
上一篇 下一篇

猜你喜欢

热点阅读