Skip to content

Latest commit

 

History

History
104 lines (77 loc) · 3.63 KB

0283.移动零.md

File metadata and controls

104 lines (77 loc) · 3.63 KB

欢迎大家参与本项目,贡献其他语言版本的代码,拥抱开源,让更多学习算法的小伙伴们收益!

# 动态规划:一样的套路,再求一次完全平方数

283. 移动零

力扣题目链接

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

示例:

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

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

思路

做这道题目之前,大家可以做一做27.移除元素

这道题目,使用暴力的解法,可以两层for循环,模拟数组删除元素(也就是向前覆盖)的过程。

好了,我们说一说双指针法,大家如果对双指针还不熟悉,可以看我的这篇总结双指针法:总结篇!

双指针法在数组移除元素中,可以达到O(n)的时间复杂度,在27.移除元素里已经详细讲解了,那么本题和移除元素其实是一个套路。

相当于对整个数组移除元素0,然后slowIndex之后都是移除元素0的冗余元素,把这些元素都赋值为0就可以了

如动画所示:

移动零

C++代码如下:

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
            if (nums[fastIndex] != 0) {
                nums[slowIndex++] = nums[fastIndex];
            }
        }
        // 将slowIndex之后的冗余元素赋值为0
        for (int i = slowIndex; i < nums.size(); i++) {
            nums[i] = 0;
        }
    }
};

其他语言版本

Java:

public void moveZeroes(int[] nums) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != 0) {
                nums[slow++] = nums[fast];
            }
        }
        // 后面的元素全变成 0
        for (int j = slow; j < nums.length; j++) {
            nums[j] = 0;
        }
    }

Python:

    def moveZeroes(self, nums: List[int]) -> None:
        slow = 0
        for fast in range(len(nums)):
            if nums[fast] != 0:
                nums[slow] = nums[fast]
                slow += 1
        for i in range(slow, len(nums)):
            nums[i] = 0

Go:

JavaScript: