本文主要是介绍Golang 数组 移除元素 双指针法 leetcode27 小记,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- 移除元素 leetcode27
- 暴力解法
- 双指针法
- 1. 快慢指针
- 2. 双向指针
移除元素 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
}
这篇关于Golang 数组 移除元素 双指针法 leetcode27 小记的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!