Golang 数组 移除元素 双指针法 leetcode27 小记

移除元素 leetcode27

  go中数据类型的分类：
1.值类型：int、float、bool、string、数组、结构体
2.引用类型：指针、切片、map、管道、接口

  由于切片为引用类型，其本质是基于数组完成的，因此我们操作切片可以理解为操作底层的数组。

暴力解法

  第一个for循环遍历切片，第二个for循环将部分数组前移

双指针法

1. 快慢指针

  双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
  在c中erase函数删除元素是将数组中当前位置后面的元素都向前移动一位，其时间复杂度为O（n）
  而go中切片的截取（s[:]和append方法），都是通过修改指向底层的数组的指针实现，对于删除头部和尾部元素的时间复杂度为O（1），中间元素的删除则同样为O（n）
  完整代码如下，包含学习过程

package mainimport "fmt"func main() {nums := []int{3, 2, 2, 3}val := 3c := removeElement(nums, val)fmt.Println(c)fmt.Println(nums)
}// 暴力解法
/*func removeElement(nums []int, val int) int {length := len(nums)if length == 0 {return 0}c := lengthfor i, v := range nums {if v == val {putOff(nums, i, val, length)c--}for nums[i] == val {putOff(nums, i, val, length)c--}}if nums[0] == val {return 0}return c
}func putOff(nums []int, i int, val int, length int) {if i == length-1 {nums[length-1] = val - 1return}nums[i] = nums[i+1]putOff(nums, i+1, val, length)
}*/// 双指针法 这里的解法还是有问题，在对应fast指针更新时，不作更新，只进行fast的右移，可以减少代码量
/*func removeElement(nums []int, val int) int {var fast, slow = 0, 0length := len(nums)for fast < length {for nums[fast] == val {fast++if fast == length {return length - fast + slow}}//if nums[slow] == val {////}nums[slow] = nums[fast]slow++fast++}return length - fast + slow
}*/// 改进双指针，最终版
func removeElement(nums []int, val int) int {var fast, slow = 0, 0length := len(nums)for fast < length {if nums[fast] != val { //如果fast对应值不是val，则可以写入nums[slow] = nums[fast]slow++}//如果fast对应等于val，则fast移位，不进行更新操作fast++}return slow
}

2. 双向指针

//相向双指针法
func removeElement(nums []int, val int) int {// 有点像二分查找的左闭右闭区间 所以下面是<=left := 0right := len(nums) - 1for left <= right {// 不断寻找左侧的val和右侧的非val 找到时交换位置 目的是将val全覆盖掉for left <= right && nums[left] != val {left++}for left <= right && nums[right] == val {right--}//各自找到后开始覆盖 覆盖后继续寻找if left < right {nums[left] = nums[right]left++right--}}fmt.Println(nums)return left
}