Algorithem_MoveZeros

Given an integer array nums, move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

Example 1:

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

Example 2:

Input: nums = [0]
Output: [0]

解法一

实现逻辑：

首先把所有非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]) {
        // 首先把所有非0的取出来
        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
        }
    }
}

解法二

实现逻辑：

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

举例如下：

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)
            }
        }
    }
}

参考

• THE EASIEST but UNUSUAL snowball JAVA solution BEATS 100% (O(n)) + clear explanation

赏

谢谢，一起进步

支付宝

微信