题目
Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example,
Given input array nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.
解题思路
对于一个排好序的数组来说，A[N + 1] >= A[N]，使用两个游标i和j来处理，假设现在i = j + 1，如果A[i] == A[j]，那么我们递增i，直到A[i] > A[j]，这时候找到了更大的值，此时递增j，再设置A[j] = A[i]，然后递增i，重复上述过程直到遍历结束。
代码
removeDuplicates.go
package _26_Remove_Duplicates_from_Sorted_Array
import "fmt"
func RemoveDuplicates(nums []int) int {
len1 := len(nums)
if 0 == len1 {
return 0
}
i, j := 1, 0
for ; i < len1; i++{
if nums[i] > nums[j]{
j++
nums[j] = nums[i]
}
}
j++
fmt.Printf("nums:%+v\n", nums)
return j
}
测试
removeDuplicates_test.go
package _26_Remove_Duplicates_from_Sorted_Array
import "testing"
func TestRemoveDuplicates(t *testing.T) {
var tests = []struct{
input []int
ret int
} {
{[]int{1, 1}, 1},
{[]int{1,1,1}, 1},
{[]int{1,2,2,3}, 3},
{[]int{-999,-999,-998,-998,-997,-997}, 3},
}
for _, v := range tests {
ret := RemoveDuplicates(v.input)
if ret == v.ret {
t.Logf("pass")
} else {
t.Errorf("fail, want %+v, get %+v", v.ret, ret)
}
}
}
