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

删除排序数组中的重复项(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...

本作品采用《CC 协议》,转载必须注明作者和本文链接
三斤
《L03 构架 API 服务器》
你将学到如 RESTFul 设计风格、PostMan 的使用、OAuth 流程,JWT 概念及使用 和 API 开发相关的进阶知识。
《L05 电商实战》
从零开发一个电商项目,功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等
讨论数量: 2
function removeDuplicates($nums) {
    $count = count($nums);
    if ($count === 0) {
        return 0;
    }

    $i = 0;
    $j = 1;
    while ($j <= $count - 1) {
        // 相等则 j 指针向后移动
        if ($nums[$j] === $nums[$i]) {
            $j++;
        } else {
            // 不想等,则 i+1 与 j 指向的元素互换,i 向后移动一位,j 向后移动一位
            $i++;
            list($nums[$i], $nums[$j]) = [$nums[$j], $nums[$i]];
            $j++;
        }
    }

    // 返回长度
//    return array_splice($nums, 0, $i+1);  // 结果集
    return $i+1;
}
echo removeDuplicates([1,2,2]);     // ouput: 2
echo removeDuplicates([1,1,2,2,3]); // ouput: 3

继续搞了 PHP 实现

1年前 评论
Littlesqx 1年前
三斤和他的喵 (楼主) 1年前
captain2021 (作者) 1年前
Littlesqx 1年前

Golang: 利用语言特点和减少不必要的临时变量,我给出的实现:

// sortDuplicate
func sortDuplicate(numArr []int) (arrLen int, arr []int) {
    for _, v := range numArr {
        if numArr[arrLen] == v {
            continue
        }
        arrLen++
        numArr[arrLen] = v
    }
    if arrLen != len(numArr) {
        arrLen++
    }
    return arrLen, numArr
}
1年前 评论
三斤和他的喵 (楼主) 1年前

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!