初级算法-数组-删除排序数组中的重复项

给你一个有序数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次 ，返回删除后数组的新长度。

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

摘一个示例做个说明.
示例 1：
输入：nums = [1,1,2]
输出：2, nums = [1,2]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。
不需要考虑数组中超出新长度后面的元素。
提示：
0 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按升序排列

条件分析:

1. 有序数组 -> 排好序了
2. 原地删除重复出现的元素,不能使用额外数组空间 -> 在原数组上操作删除
3. 每个数组只出现一次 -> 去重
4. 返回删除后的新长度 -> 有效的length
5. 使用O(1)额外空间 -> 只能内容定义一个变量
6. !隐藏消息即示例中 不考虑数组中超出新长度的元素 -> 数组有效长度内容为真,超出后的不重要

解决思路1:

1. 根据分析2,说明数组操作是指针操作,不开辟新空间.
2. 根据分析5,说明我们需要从前往后判断数据是否重复,对不重复的数据要覆盖重复数据,以保证有效长度内数据为真.

传入数组地址,先判空,如果空则return.然后循环判断数据是否重复.因为是新长度即可,所以采用双指针实现.left指针保留前值,right指针进行数据获取用以对比.如果left、right数据相同,right右移(即正常循环,左指针位置不变,除循环外,不做任何处理);如果left、right数据不同(因为数组是有序数组,所以肯定是左指针数据小于等于右指针数据),left右移一位,然后赋值其为right值;right再继续右移进行对比(赋值完成后,继续循环).依次类推,直到结束.最后返回left+1即为删除后的新长度.

解决思路2:

采用循环删除的方法,分析2,5同上,说明我们需要从采用遍历删除,如果相同,则删除,最后数组的数据就是新数组

代码实现-Swift版本:
oc版本都不能提交,就不演示了.有兴趣的可以自己试一下即可.

思路1代码:

func removeDuplicates(_ nums: inout[Int]) -> Int {
    /// 先判空
    if nums.count == 0 {
        return 0
    }
    /// 左指针
    var left = 0
    /// 右指针
    for right: Int in 1 ..< nums.count {
        /// 如果左指针数据不等于右指针数据
        if nums[left] != nums[right] {
            /// 左指针右移一位,然后左指针赋值右指针内容
            left += 1
            nums[left] = nums[right];
        }
    }
    
    /// 左指针长度加1,即为新数组的长度,指针后面的数据属于无用数据
    return left + 1
}

思路1提交结果.jpg

由于系统有数组数据调换API,所以也可以采用API形式
思路1代码优化:

func removeDuplicates(_ nums: inout [Int]) -> Int {
    if nums.count == 0 {
        return 0
    }
    
    var left = 0
    for right in 1 ..< nums.count {
        //因为数组是有序数组,所以肯定是左指针数据小于等于右指针数据
        if nums[left] < nums[right] {
            left += 1
            nums.swapAt(left, right)
        }
    }

    return left + 1
}

思路1 优化 提交结果.jpg

思路2代码:

func removeDuplicates(_ nums: inout [Int]) -> Int {
    if nums.count == 0 || nums.count == 1 {
        return nums.count
    }
    for i in (1 ..< nums.count).reversed() {
        if nums[i] == nums[i - 1] {
            nums.remove(at: i)
        }
    }

    return nums.count
}

思路2提交结果.jpg

测试用例:

// 无数据情况
var nums0: [Int] = []
// 只有一个元素
var nums1: [Int] = [1]
// 只有两个相同元素
var nums2: [Int] = [1,1]
// 只有两个不相同元素
var nums3: [Int] = [1,3]
// 首尾有相同元素
var nums4: [Int] = [1,1,2,3,4,6,7,8,9,9]
// 首尾和中间有相同元素
var nums5: [Int] = [1,1,2,3,4,4,6,7,8,9]
// 没有相同元素
var nums6: [Int] = [1,2,3,4,5,6,7,8,9]

做个简单说明,nums不能是let,因为需要对数组进行操作,其次nums不能定义Array<Int> 因为内容可变.

考察要点:

• 数组
• 双指针