嗨,这个假期罗根开始接触了算法,在为今年的蓝桥杯做准备。
所以,开个新专栏,记录记录自己做算法题时的心得~
一、题目
给定一个数组?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;
}
}
}
}
以上就是本篇博客的全部内容啦,如有不足之处,还请各位指出,期待能和各位一起进步!