【算法-初级-数组】删除排序数组中的重复项(多语言版实现)

【算法-初级-数组】删除排序数组中的重复项(多语言版实现)

???? 博客说明与致谢

???????????? 文章所涉及的部分资料来自互联网整理,其中包含自己个人的总结和看法,分享的目的在于共建社区和巩固自己。

???????????? 引用的资料如有侵权,请联系本人删除!

❤️‍????❤️‍????❤️‍???? 感谢万能的网络!

???????????? 以及勤劳的自己个人博客GitHub学习GitHub

???????????? 公众号【归子莫】,小程序【子莫说】

???????????? 如果你感觉对你有帮助的话,不妨给我点赞鼓励一下,好文记得收藏哟!关注我一起成长!

???????????? 幸好我在,感谢你来!

???? 算法说明

语言只是实现算法的一种手段,思路才是最为重要的。

如果有多种解法的话,只选一种语言作为解答对比。

如果单独将某一种算法的话,会以多种语言实现,对比语言的特性。

????因为多对多的话,篇幅会拉的比较大,影响观看体验!

???? 题目

地址

26. 删除有序数组中的重复项

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

题目说明

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

说明

为什么返回数值是整数,但输出的答案是数组呢?

请注意,输入数组是以「引用」方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说,不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

示例 1

输入:nums = [1,1,2]
输出:2, nums = [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]
解释:函数应该返回新的长度 5 , 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示

0 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按升序排列

???? 思路

暴力想法

(注意是暴力想法,不是暴力解法!)

作为直男直接就是想实现。

直接遍历,看题目是已经确定了是有序的,遇到与上一个不相等的直接给他拿到新的数组里面存起来。遍历完直接新数组就是答案。

看样子是很接近了哈!毕竟属于简单的题目。

但是O(1) 额外空间的条件下完成这个是我们跨不过去的坎。既然如此那就得考虑在原数组上操作。

原数组上操作,先上双指针!

双指针

思路

快慢指针上场,快指针fast,慢指针low

数组是有序的,那么重复的元素一定会相邻。在同一个数组里面操作,也就是不重复的元素移到数组的左侧,最后取左侧的数组的值。

算法流程

  • 比较 fast low 位置的元素是否相等。

    • 循环执行:

      • 如果相等,fast 后移 1 位
      • 如果不相等,将low前一位的值改为fastlow 后移1位,fast 后移 1 位
    • 循环结束:

      • fast越界
  • 循环结束,返回新数组长度 low + 1

图解

这将是最具有灵魂的一刻了。没有图解的算法都是耍流氓!(哈哈哈,我会尽量把我之前的流氓行为更正过来哈!)

其实画图花了我很多的时间,但我觉得不亏,记得更深刻!

来个GIF吧!(用Python写了一个将图片生成GIF的小工具)

【算法-初级-数组】删除排序数组中的重复项(多语言版实现)JavaScript

没有什么特别好说的,强行来一句的话,就是把nums的长度计算拿上去,节约成本。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    // 判断边界
    if (nums && nums.length < 0) {
        return 0
    }
    var low = 0, fast = 1, n = nums.length;
    while (fast < n) {
        if (nums[fast] !== nums[low]) {
          nums[low + 1] = nums[fast]
            low++  
        } 
        fast++
    }
    return low + 1
};

Java

代码

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length < 1) {
            return 0;
        }
        int fast = 1, low = 0, n = nums.length;
        while(fast < n) {
            if (nums[fast] != nums[low]){
                nums[low + 1] = nums[fast];
                low++;
            }
            fast++;
        }
        return low + 1;
    }
}

Python3

代码

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0
        n = len(nums)
        fast = 1
        low = 0
        while fast < n:
            if nums[fast] != nums[low]:
                nums[low + 1] = nums[fast]
                low += 1
            fast += 1
        return low + 1

PHP

代码

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function removeDuplicates(&$nums) {
        if ($nums == null || count($nums) < 0) {
            return 0;
        }
        $fast = 1;
        $low = 0;
        $n = count($nums);
        while ($fast < $n) {
            if ($nums[$fast] != $nums[$low]) {
                $nums[$low + 1] = $nums[$fast];
                $low++;
            }
            $fast++;
        }
        return $low + 1;
    }
}

Go

注意go语言是没有while的

代码

func removeDuplicates(nums []int) int {
    n := len(nums)
    if n < 1 {
        return 0
    }
    low := 0
    for fast := 1; fast < n; fast++ {
        if nums[fast] != nums[low] {
            nums[low + 1] = nums[fast]
            low++
        }
    }
    return low + 1
}

C++

代码

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        if (n < 1) {
            return 0;
        }
        int fast = 1, low = 0;
        while (fast < n) {
            if (nums[fast] != nums[low]) {
                nums[low + 1] = nums[fast];
                low++;
            }
            fast++;
        }
        return low + 1;
    }
};

C

代码

int removeDuplicates(int* nums, int numsSize){
    if(numsSize == 0) {
        return 0;
    }
    int fast = 1, low = 0;
    while (fast < numsSize) {
        if (nums[fast] != nums[low]) {
            nums[low + 1] = nums[fast];
            low++;
        }
        fast++;
    }
    return low + 1;
}

???? 总结

从数组开始,思考 ???? 数组提该如何提炼思路,从简单到复杂一步一步拆解,也将编程语言的数据使用技能提升。

上一篇:轻松上手ECS云服务器--MySQL数据库进阶实战


下一篇:linux安装python