【算法刷题】Day7_代码007(未授权)

本文介绍: 我们这里可以运用**“双指针”**的方法这里的双指针，并不是 c 语言中的指针，而是用数组模拟的指针。看到题目，首先看一下题干的要求，是在原数组内进行操作，平切保持非零元素的相对顺序。遇到非零元素：swap(dest+1,cur);首先先看题干，把数组中每个零都复写一遍，其他元素水平右移，并且就地修改。这个时候，数组就被 cur 和 dest 分成了三个区间。dest：已处理的区间内，在非零元素的最后一个位置。我们要定义两个“指针”，cur 和 dest。[ dest+1, cur-1 ] 0元素。

在这里插入图片描述
原题链接

看到题目，首先看一下题干的要求，是在原数组内进行操作，平切保持非零元素的相对顺序

这个时候我们看到了示例一：
[ 0, 1, 0, 3,12 ]
这个时候输出成为了
[ 1, 3, 12, 0, 0 ]

我们这里可以运用**“双指针”**的方法这里的双指针，并不是 c 语言中的指针，而是用数组模拟的指针

首先：
我们要定义两个“指针”，cur 和 dest
cur：从左往右扫描数组，遍历数组
 des t：已处理的区间内，在非零元素的最后一个位置

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

public void duplicateZeros(int[] arr) {
        int cur = 0;
        int dest = -1;
        int n = arr.length;
        //1、找到最后一个需要复写的数
        while (cur < n) {
            if (arr[cur] == 0) {
                dest += 2;
            }else {
                dest += 1;
            }
            if (dest &gt;= n-1) {
                break;
            }
            cur++;
        }
        //2、处理边界情况
        if (dest == n) {
            arr[n - 1] = 0;
            cur--;
            dest -= 2;
        }
        //3、从后向前完成复写操作
        while (cur &gt;= 0) {
            if(arr[cur] != 0) {
                arr[dest--] = arr[cur--];
            }else {
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }
    }