今是昨非

今是昨非

日出江花红胜火,春来江水绿如蓝

算法_移动零

移动零算法#

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

注意,您必须在原地进行操作,不能使用额外的数组副本。

示例 1:


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

示例 2:


输入: nums = [0]
输出: [0]

解法一#

实现逻辑:

首先将所有非零元素放在数组的前面,并记录非零元素的个数,然后将非零元素之后的元素置为 0。

举例如下:


nums = [1, 0, 2, 3, 0, 6]

j = 0 
遍历数组:
i = 0,nums[0] = 1, != 0, num[j] = num[i], j + 1, [1, 0, 2, 3, 0, 6]
i = 1, nums[1] = 0, 
i = 2, nums[2] = 2, != 0, num[j] = num[i], j + 1, [1, 2, 2, 3, 0, 6]
i = 3, nums[3] = 3, != 0, num[j] = num[i], j + 1, [1, 2, 3, 3, 0, 6]
i = 4, nums[4] = 0, 
i = 5, nums[5] = 6, != 0, num[j] = num[i], j + 1, [1, 2, 3, 6, 0, 6]

// 将从 j 开始到数组末尾的元素置为0
j = 4, [1, 2, 3, 6, 0, 0]


代码如下:


class Solution {
    
    func moveZeroes(_ nums: inout [Int]) {
        // 首先将所有非零元素取出来
        var j = 0
        
        for i in 0..<nums.count {
            if nums[i] != 0 {
                // 当前元素不为0
                // j从0开始
                nums[j] = nums[i]
                j = j + 1
            }    
        }
        
        // 将从 j 开始到数组末尾的元素置为0
        while j < nums.count {
            nums[j] = 0
            j = j + 1
        }
    }
}

解法二#

实现逻辑:

定义一个变量 snowballSize 来表示数组中 0 的个数,遍历数组,如果当前元素是 0,则将 snowballSize 加 1,如果当前元素不为 0 且 snowballSize 大于 0,则交换当前元素和前面 snowballSize 个元素的位置。

举例如下:


nums = [1, 0, 2, 3, 0, 6]

snowballSize = 0 
遍历数组:
i = 0,nums[0] = 1, snowballSize = 0;
i = 1, nums[1] = 0, snowballSize += 1;
i = 2, nums[2] = 2, snowballSize > 0, swap(i, i - snowballSize), [1, 2, 0, 3, 0, 6]
i = 3, nums[3] = 3, snowballSize > 0, swap(i, i - snowballSize), [1, 2, 3, 0, 0, 6]
i = 4, nums[4] = 0, snowballSize += 1;
i = 5, nums[5] = 6, snowballSize > 0, swap(i, i - snowballSize), [1, 2, 3, 6, 0, 0]

代码如下:


class Solution {
    func moveZeroes(_ nums: inout [Int]) {
        // 定义含0的长度
        var snowballSize = 0
        
        // 遍历数组
        for index in 0..<nums.count {
            let num = nums[index]
            // 如果当前元素为0,则含0长度字段加1
            if num == 0 {
                snowballSize += 1
            }
            else if snowballSize >= 1 {
                // 如果当前含0字段长度大于1,则交换当前元素和前一个元素的位置
                nums.swapAt(index, index-snowballSize)
            }
        }
    }
}

参考#

加载中...
此文章数据所有权由区块链加密技术和智能合约保障仅归创作者所有。