让我们一起啃算法----删除排序数组中的重复项

删除排序数组中的重复项（Remove-Duplicates-From-Sorted-Array）

题干如下：

给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 1:
  给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 你不需要考虑数组中超出新长度后面的元素。
示例 2:
  给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。你不需要考虑数组中超出新长度后面的元素。
来源：力扣

这个题目有两个注意点：

• 源数组是有序的，并且是从小到大的
• 解题的过程中不能引入新的数组

解题思路

其实刷的题多了之后，碰到 数组 或者 字符串 类型的题目，第一反应就是 双指针思路，这题的解题思路主要应用的也是 双指针。

首先初始化 i 指向第一个元素， j 指向第二个元素。接着比较 arr[i] 与 arr[j] 的大小：当 arr[i] 与 arr[j] 相等时，i 不动，j 向后移动一位；当 arr[i] 与 arr[j] 不等时，将 arr[i+1] 与 arr[j] 互换，之后 i++，j++。以此类推，直到 j 越界。

流程图如下：

代码实现

GO实现

// nums是有序的，并且是从小到大的
func removeDuplicates(nums []int) int {
    if len(nums) <= 0 {
        return 0
    }
    i := 0
    j := 1

    for j <= len(nums) -1 {

        // 相等，则 j++
        if nums[j] == nums[i] {
            j++
        } else {
                // 不想等，则 i+1 与 j 指向的元素互换，i 向后移动一位，j 向后移动一位
            i++
            nums[i], nums[j] = nums[j], nums[i]
            j++
        }
    }
    // 返回长度
    return i + 1
}

总结

每天进步一点点，加油！
算法教程项目，每天更新一题，点个 star 支持一下呀：
https://github.com/wx-satellite/learning-a...

有疑问加站长微信联系（非本文作者）