leetcode｜别说你不知道双指针

今天是 Kevin 的算法之路的第 10 天。为大家讲解 LeetCode 第 283 题，是一道常考的双指针应用题，这周计划给大家带来「数组」的面试相关题，数组作为基础且常考的数据结构，有必要重视一下。

每日一笑

生活百分之八十的痛苦来自工作，但是我知道，我不工作的话，生活百分之百的痛苦来自没钱，所以上班和没钱中间，我选择了工作。

题目描述

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

示例:

输入: [0,1,0,3,12]

输出: [1,3,12,0,0]

说明:

必须在原数组上操作，不能拷贝额外的数组。

尽量减少操作次数。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/move-zeroes

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

快慢双指针

我们创建两个指针 a 和 b，a 用于寻找非0元素，b 用于接受非0元素的赋值，所以遍历一次完后所有的非0元素 在 b 指针之前，最后在将 b 指针之后的元素赋值为 0 即可。

如下动图所示

代码实现

// go
funcmoveZeroes(nums []int)  {
if nums == nil {
return
 }
 b := 0
for a := 0; a < len(nums); a++ {
if nums[a] != 0 {
   nums[b] = nums[a]
   b++
  }
 }
for i := b; i < len(nums); i++ {
  nums[i] = 0
 }
}

// java
classSolution{
publicvoidmoveZeroes(int[] nums){
if(nums==null) {
return;
  }
//第一次遍历的时候，j指针记录非0的个数，只要是非0的统统都赋给nums[j]
int j = 0;
for(int i=0;i<nums.length;++i) {
if(nums[i]!=0) {
    nums[j++] = nums[i];
   }
  }
//非0元素统计完了，剩下的都是0了
//所以第二次遍历把末尾的元素都赋为0即可
for(int i=j;i<nums.length;++i) {
   nums[i] = 0;
  }
 }
}

时间复杂度:O(n) (虽然是两次遍历 n+n = 2n，但常数无影响，还是 n 级别的复杂度)

空间复杂度:O(1)

快速排序

我们可以参考快排的思想，快速排序首先要确定一个待分割的元素做中间点x，然后把所有小于等于x的元素放到x的左边，大于x的元素放到其右边。

这里我们将0当做这个中间点，把不等于0的放到中间点的左边，等于0的放到其右边。我们使用两个指针a和b，只要nums[a]!=0，我们就交换nums[a]和nums[b]

如下动图所示

代码实现

funcmoveZeroes(nums []int)  {
if nums == nil {
return
    }
    b := 0
for a:=0; a< len(nums); a++ {
if nums[a] != 0 {
             nums[a], nums[b] = nums[b], nums[a]
             b++
        }
    }
}

classSolution{
publicvoidmoveZeroes(int[] nums){
if(nums==null) {
return;
  }
//两个指针i和j
int j = 0;
for(int i=0;i<nums.length;i++) {
//当前元素!=0，就把其交换到左边，等于0的交换到右边
if(nums[i]!=0) {
int tmp = nums[i];
    nums[i] = nums[j];
    nums[j++] = tmp;
   }
  }
 }
}

时间复杂度:O(n)

空间复杂度:O(1)

郑重声明：

所展示代码已通过 LeetCode 运行通过，请放心食用～

在唠唠嗑

很多人都想养成好习惯，但大多数人却是三分钟热度。为了我们能一起坚持下去，决定制定如下计划（福利）

一起学算法，打卡领红包！

参与方式：

关注我的微信公众号「Kevin的学堂」

还可「组团」与众多小伙伴

一起坚持，一起学习，一起更优秀！

打卡规则为：

「留言」“打卡XXX天” ➕「分享」到朋友圈

奖励：

连续打卡 21 天，联系本人获取 6.6 元红包一个！

连续打卡 52 天，联系本人获取 16.6 元红包一个！

连续打卡 100 天，联系本人获取 66.6 元红包一个！

本文使用 mdnice 排版