移除元素

27. 移除元素

题目

27. 移除元素

解题思路

勿用质疑，双指针

方法一：快慢指针，快指针指向当前需要检查的元素地址，慢指针指向需要保存的地址

方法二：双指针，由于所有等于val的元素最终都要放在数组后面位置，所以left指针可以指向最后已检查的元素，right指针指向最后需检查的元素后一位

方法二内存交换会少一些

复杂度

需要遍历一遍数组，未申请内存

时间复杂度：O(n)

空间复杂度：O(1)

Code

方法一：

func removeElement(nums []int, val int) int {
    var (
        curr = 0
        p = 0
    )
    for ;p<len(nums);p++{
        if nums[p] != val{
            nums[curr] = nums[p]
            curr++
        }
    }
    return curr
}

方法二：

func removeElement(nums []int, val int) int {
	var (
		left = 0
		right = len(nums)
	)
	for left < right {
		if nums[left] == val {
			nums[left] = nums[right - 1]
			right--
		}else {
			left++
		}
	}
	return left
}