双指针练习题移动零

Bertha 。 2024-05-06 21:20 55阅读 0赞

![previewfile\_1962375063][previewfile_1962375063]

[283. 移动零][283.]

#### 1.题目要求: ####

给定一个数组 `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`

#### 2.算法原理 ####

> 数组划分/数组分块

解决: 双指针算法(利用数组下标来充当指针)

![image-20240202203950750][]

> cur => current: 当前的  
> dest => destination: 目的地

两个指针的作用:  
cur: 从左往右扫描数组，遍历数组  
dest: 已处理的区间内，非零元素的最后一个位置

![image-20240202213444834][]

![image-20240202221836398][]

三个区间：\[0,dest\], \[dest+1,cur-1\], \[cur,n-1\]  
\[0,dest\]：非零元素  
\[dest+1,cur-1\]：0元素  
\[cur,n\]：待处理元素

![image-20240202225702551][]

以示例1为例, nums = \[0,1,0,3,12\], 画图说明

![image-20240203195128437][]

![image-20240203200006664][]

![image-20240203203600333][]

> cur从前往后遍历的过程中:
> 
> 1.  遇到0元素: cur++;
> 2.  遇到非零元素: swap(dest + 1, cur);/*自定义的交互函数*/ dest++,cur++;

#### 3.编写代码 ####

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;
                }
            }
        }
    }

#### 4.**运行结果** ####

![image-20240203205403716][]

[previewfile_1962375063]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/c9d2e06541c843c1a852d3c919a8488e.jpeg
[283.]: https://leetcode.cn/problems/move-zeroes/
[image-20240202203950750]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/550c3fe70520450abe525b3fd03651f0.png
[image-20240202213444834]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/b35264efb59042e0a8061ac634d41493.png
[image-20240202221836398]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/764c28c145104a128ae5dcfe8b11648e.png
[image-20240202225702551]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/5d48aa19eb9743b5bc1a65d1b68763a6.png
[image-20240203195128437]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/d69a59f58b01451b99c665225ff8c270.png
[image-20240203200006664]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/424c5e4f73924b68b8f7226b69dfa656.png
[image-20240203203600333]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/1af399b4023747959402a446eedb4954.png
[image-20240203205403716]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/de21dca48a274fb8a92e5cf7b27e693a.png