[双指针](一) Leetcode 283.移动零和1089.复写零

[双指针] Leetcode 283.移动零和1089.复写零

移动零

283. 移动零

1.题意分析

(1) 给你一个数组，将数组中的所有0移动到数组的末尾

(2) 保证非0元素在数组中相对位置不变

(3) 在原数组中操作

2.解题思路

由于题目要求我们移动数组内容（也就是交换两个数的位置），所以我们很容易想到双指针解法。

解法：双指针

定义两个“指针”(left 和 right)，right遍历整个数组，遇到0就交换两个数的位置。

nums[right] == 0：right++;

nums[right] != 0：swap(nums[right],    nums[left]),  right++, left++
1
2
3

示例1：[0, 1, 0, 3, 12]

请先自己尝试实现代码，再来继续往下看。

---

3.代码实现

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        for(int left = 0, right = 0; right < nums.size(); )
        {
            if(nums[right] != 0) swap(nums[left++], nums[right++]);
            else right++;
        }
    }
};
1
2
3
4
5
6
7
8
9
10

4.总结

细节1：right的大小由我们自己在if-else控制，并不需要写入循环。

细节2：right的大小超过数组的size即为遍历完整个数组。

复习零

1089. 复写零

1.题意分析

(1) 给你一个长度固定的数组，将数组中的0再次写一遍，即为在0后再加一个0

(2) 其余的数向右平移

(3) 超过数组长度，终止写入元素

(4) 在原数组上进行操作

2.解题思路

题目要求我们进行复写0，即需要知道两个数的位置，所以可以使用两个“指针”，一前一后：判断0，添加0。

解法：双指针

由于数组空间是固定的，我们首先需要知道最后一个数的位置，然后倒着进行修改数组。

nums[i] == 0：count+= 2;

nums[i] != 0：count++;

count >= nums.size-1：break;

i++;
1
2
3
4
5
6
7

i即为新数组的最后一个数，我们在倒着写回数组。

nums[i] == 0：nums[count] = 0, count[count-1] = 0, i--, count -= 2;

nums[i] != 0：nums[count] = nums[i], i--, count--。
1
2
3

示例1：

nums[] = [1, 0, 2, 3, 0, 4, 5, 0]

注意处理这样的数组: nums[] = {8, 4, 5, 0, 0, 0, 0, 7}

请先自己尝试实现代码，再来继续往下看。

---

3.代码实现

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        //1.计算数组最后一个位置
        int count = -1, i = 0, n = arr.size();
        while(count < n)
        {
            if(arr[i] != 0) count++;
            else count += 2;
            if(count >= n-1) break;
            i++;
        }
        //处理特殊情况
        if(count == n)
        {
            arr[n-1] = 0;
            i--;
            count -= 2;
        }
        //2.逆向填充数组
        while(i >= 0)
        {
            if(arr[i] != 0) arr[count--] = arr[i--];
            else 
            {
                arr[count--] = 0;
                arr[count--] = 0;
                i--;
            }
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

4.总结

细节1：count为什么初始化为-1：因为数组下标是从0开始的，从-1开始可以和数组下标对应上，不会越界；从0开始最后又得减掉，后续处理十分麻烦。

细节2：求最后的复写数时，循环中if(count >= n-1) break;：如果此时count已经大过数组的size-1(也就是超出数组的范围)，就没有必要再让当前的下标i再加1了。

细节3：nums[] = {8, 4, 5, 0, 0, 0, 0, 7}：这样的数组，我们最后复写出来的结果为{8, 4, 5, 0, 0, 0, 0, 0}因为第三个0，会有一个0复写时越界了，我们之前的算法无法处理这种特殊情况，需要我们手动处理一下：count == nums.size时，将数组的最后一位手动赋值0，最后复写的数的下标i应该-1，而count应该-2(看不懂就画一下图)。

END, THANKS。