算法【一】

标签：arr cur dest 元素 算法 数组 复写

题目： 

283. 移动零 - 力扣（LeetCode）

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

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

示例 1:

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

示例 2:

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

提示:

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

算法思路： 在本题中，我们可以⽤⼀个 cur 指针来扫描整个数组，另⼀个 dest 指针⽤来记录⾮零数序列 的最后⼀个位置。根据 cur 在扫描的过程中，遇到的不同情况，分类处理，实现数组的划分。 在 cur 遍历期间，使 [0, dest] 的元素全部都是⾮零元素， [dest + 1, cur - 1] 的 元素全是零。 算法流程： a. 初始化 cur = 0 （⽤来遍历数组）， dest = -1 （指向⾮零元素序列的最后⼀个位置。 因为刚开始我们不知道最后⼀个⾮零元素在什么位置，因此初始化为 -1 ） b. cur 依次往后遍历每个元素，遍历到的元素会有下⾯两种情况： i. 遇到的元素是 0 ， cur 直接 ++ 。因为我们的⽬标是让 [dest + 1, cur - 1] 内 的元素全都是零，因此当 cur 遇到 0 的时候，直接 ++ ，就可以让 0 在 cur - 1 的位置上，从⽽在 [dest + 1, cur - 1] 内； ii. 遇到的元素不是 0 ， dest++ ，并且交换 cur 位置和 dest 位置的元素，之后让 cur++ ，扫描下⼀个元素。 因为 dest 指向的位置是⾮零元素区间的最后⼀个位置，如果扫描到⼀个新的⾮零元 素，那么它的位置应该在 dest + 1 的位置上，因此 dest 先⾃增 1 ； dest++ 之后，指向的元素就是 0 元素（因为⾮零元素区间末尾的后⼀个元素就是 0 ），因此可以交换到 cur 所处的位置上，实现 [0, dest] 的元素全部都是⾮零 元素， [dest + 1, cur - 1] 的元素全是零。

代码：

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

题目：1089. 复写零 - 力扣（LeetCode）

给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。

注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。

示例 1：

输入：arr = [1,0,2,3,0,4,5,0]
输出：[1,0,0,2,3,0,0,4]
解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]

示例 2：

输入：arr = [1,2,3]
输出：[1,2,3]
解释：调用函数后，输入的数组将被修改为：[1,2,3]

提示：

• 1 <= arr.length <= 104
• 0 <= arr[i] <= 9

算法思路： 如果「从前向后」进⾏原地复写操作的话，由于 0 的出现会复写两次，导致没有复写的数「被覆 盖掉」。因此我们选择「从后往前」的复写策略。 但是「从后向前」复写的时候，我们需要找到「最后⼀个复写的数」，因此我们的⼤体流程分两 步：   i. 先找到最后⼀个复写的数；   ii. 然后从后向前进⾏复写操作。 算法流程：   a. 初始化两个指针 cur = 0 ， dest = 0 ；   b. 找到最后⼀个复写的数：        i. 当 cur < n 的时候，⼀直执⾏下⾯循环：        判断 cur 位置的元素:        如果是 0 的话， dest 往后移动两位；        否则， dest 往后移动⼀位。           判断 dest 时候已经到结束位置，如果结束就终⽌循环；           如果没有结束， cur++ ，继续判断。 c. 判断 dest 是否越界到 n 的位置：       i. 如果越界，执⾏下⾯三步：              1. n - 1 位置的值修改成 0 ；              2. cur 向移动⼀步；              3. dest 向前移动两步。 d. 从 cur 位置开始往前遍历原数组，依次还原出复写后的结果数组：      i. 判断 cur 位置的值：                1. 如果是 0 ： dest 以及 dest - 1 位置修改成 0 ， dest -= 2 ；                2. 如果⾮零： dest 位置修改成 0 ， dest -= 1 ；      ii. cur-- ，复写下⼀个位置。

代码：

class Solution {
    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++;
            }
            if(dest>=n-1){
                break;
            }
            cur++;
        }
        //2.处理一下边界情况
        if(dest==n){
            arr[n-1]=0;
            cur--;
            dest-=2;
        }
        //3.从后往前复写
        while(cur>=0){
            if(arr[cur]!=0){
                arr[dest--]=arr[cur--];
            }else{
                arr[dest--]=0;
                arr[dest--]=0;
                cur--;
            }
        }
    }
}

标签：arr,cur,dest,元素,算法,数组,复写
From： https://blog.csdn.net/2401_86415114/article/details/144225479