03/80 删除排序数组中的重复项

题目描述

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持一致。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组 nums 的第一部分。更具体地，如果在删除重复项后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

注意： 不要使用额外的空间，你必须在 原地修改输入数组 并在使用 $O(1)$ 额外空间的条件下完成。

---

核心思路：快慢指针

这道题是“双指针”技巧中最经典的应用场景之一。

1. 快慢指针定义：
   • **慢指针 slow**：指向当前已确定的不重复序列的最后一个位置。
   • **快指针 fast**：遍历整个数组，寻找下一个不重复的元素。
2. 移动逻辑：
   • 初始时，slow 指向索引 0。
   • fast 从索引 1 开始向后遍历。
   • 当 nums[fast] != nums[slow] 时，说明找到了一个新元素。此时：
     • slow 向后移一位（slow++）。
     • 将 nums[fast] 的值赋给 nums[slow]。
3. 最终结果：
   • 由于 slow 是索引，最终不重复数组的长度就是 slow + 1。

---

代码实现 (Kotlin)

class Solution {
    /**
     * 删除排序数组中的重复项
     * @param nums 升序排列的整数数组
     * @return 剔除重复项后数组的新长度
     */
    fun removeDuplicates(nums: IntArray): Int {
        // 1. 边界处理：若数组为空，长度为 0
        if (nums.isEmpty()) return 0
        
        // 2. 初始化慢指针
        var slow = 0
        
        // 3. 快指针 fast 遍历数组
        for (fast in 1 until nums.size) {
            // 如果快指针指向的元素与慢指针不同
            if (nums[fast] != nums[slow]) {
                // 慢指针后移，并更新其位置的值
                slow++
                nums[slow] = nums[fast]
            }
        }
        
        // 4. 返回长度（索引 + 1）
        return slow + 1
    }
}

fun main() {
    val solution = Solution()
    val nums = intArrayOf(0, 0, 1, 1, 1, 2, 2, 3, 3, 4)
    val length = solution.removeDuplicates(nums)
    
    println("处理后的数组长度: $length")
    print("数组内容: ")
    for (i in 0 until length) {
        print("${nums[i]} ")
    }
}

---

复杂度分析

• 时间复杂度：$O(N)$。其中 $N$ 是数组的长度。快指针 fast 遍历一次数组即可完成。
• 空间复杂度：$O(1)$。我们只使用了常数级别的额外空间（两个指针变量），完全在原地进行修改。

---

关键点总结

1. **原地修改 (In-place)**：题目明确要求不能创建新数组，因此双指针覆盖原有位置是唯一高效的做法。
2. 升序前提：因为数组是有序的，所以重复的元素必然是相邻的。这使得我们只需要比较 nums[fast] 和 nums[slow] 即可判断是否重复。
3. 通用扩展：
   • 如果题目要求 “每个元素最多出现两次” 怎么办？
   • 逻辑只需改为：nums[fast] != nums[slow - 1] 即可实现允许重复两次的逻辑。