双指针应用题

题目:

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

示例:

输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 说明:

必须在原数组上操作,不能拷贝额外的数组。尽量减少操作次数。

解题思路:

1.快慢双指针

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

func moveZeroes(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
 }
}

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

2.快速排序

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

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

func moveZeroes(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++
        }
    }
}

  地址:https://mp.weixin.qq.com/s/trlkpIcn1xgkrOGaA6cd1Q

原文地址:https://www.cnblogs.com/smallleiit/p/13303756.html