移除元素 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 main
import "fmt"
func main() {
nums := []int{
3, 2, 2, 3}
val := 3
c := 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 := length
for 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 - 1
return
}
nums[i] = nums[i+1]
putOff(nums, i+1, val, length)
}*/
// 双指针法 这里的解法还是有问题，在对应fast指针更新时，不作更新，只进行fast的右移，可以减少代码量
/*func removeElement(nums []int, val int) int {
var fast, slow = 0, 0
length := 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, 0
length := 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 := 0
right := len(nums) - 1
for 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
}
