「优选算法刷题」:移动零

发布时间:2024年01月17日

嗨,这个假期罗根开始接触了算法,在为今年的蓝桥杯做准备。

所以,开个新专栏,记录记录自己做算法题时的心得~

一、题目

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

请注意?,必须在不复制数组的情况下原地对数组进行操作。

示例 1:

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

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

示例 2:

输入: 
nums = [0]

输出: 
[0]

二、思路解析

其实这种题,都可以划分为「数组划分」这一大类,适合用 「双指针」 解答。

在 C 语音中的双指针,总是要定义一堆 int * ,看完简直头皮发麻。

而在 Java 中,则不用那么麻烦,因为我们是直接利用数组下标来充当指针的。

So,我们定义一个 cur 指针「快指针」和 一个 dest 指针「慢指针」,作用分别如下:

并且,在初始化的时候,cur 为 0,dest 为 -1「不能赋值为 0 是要考虑到第一个元素值为?0 的情况」。

好,回到这道题,我们要把所有值为 0 的元素全部放到数组最末端。

也就是说,在处理过程中,一共会有以下三种区间:

明确了这些,我们就让 cur 指针在从前向后遍历的过程中:

情况1??:遇到值为 0 的元素,就向后移动一位;

情况2??:遇到值不为 0 的元素,就交换下标为 cur 和 dest 的元素的值,然后两个指针都向后移动 1 位?

以上,即可完成题目。

三、完整代码

class Solution {

    public void moveZeroes(int[] nums) {
        int cur = 0;
        int dest = -1;
        for(dest=-1;cur<nums.length;cur++){
            if(nums[cur] != 0){
                dest++;
                int tmp;
                tmp = nums[cur];
                nums[cur] = nums[dest];
                nums[dest] = tmp;
            }
        }
    }
}

以上就是本篇博客的全部内容啦,如有不足之处,还请各位指出,期待能和各位一起进步!

文章来源:https://blog.csdn.net/C_Small_Cai/article/details/135648852
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。