【经典算法】LeetCode 26. 删除有序数组中的重复项:(Java/C/Python3实现含注释说明,Easy)

简介: 【经典算法】LeetCode 26. 删除有序数组中的重复项:(Java/C/Python3实现含注释说明,Easy)

题目描述

给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。

不要使用额外的数组空间,你必须在原地修改输入数组并在使用 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。
你不需要考虑数组中超出新长度后面的元素。

说明:

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

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

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

// nums 是以“引用”传递的。也就是说,不对实参作任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

原题:LeetCode 26 删除有序数组中的重复项

思路及实现

方式一:双指针法

思路

利用双指针法,一个指针用于遍历数组,另一个指针指向不重复序列的末尾,即下一个要插入不重复元素的位置。遍历数组时,如果当前元素与前一个元素(即不重复序列的末尾元素)不同,则将该元素插入不重复序列末尾,并移动末尾指针。

代码实现

Java版本
public int removeDuplicates(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    
    int i = 0; // 慢指针,指向不重复序列的末尾
    for (int j = 1; j < nums.length; j++) { // 快指针,遍历数组
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j];
        }
    }
    
    return i + 1; // 返回不重复序列的长度
}

说明:

  • 如果数组为空或长度为0,直接返回0。
  • 初始化慢指针i为0,指向不重复序列的第一个元素。
  • 遍历数组,如果当前元素nums[j]与慢指针指向的元素nums[i]不同,说明找到了一个新的不重复元素,将其插入不重复序列末尾,并移动慢指针i
  • 最后返回i + 1,因为i是指向不重复序列末尾的下一个位置。
C语言版本
int removeDuplicates(int* nums, int numsSize) {
    if (nums == NULL || numsSize == 0) {
        return 0;
    }
    
    int i = 0; // 慢指针,指向不重复序列的末尾
    for (int j = 1; j < numsSize; j++) { // 快指针,遍历数组
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j];
        }
    }
    
    return i + 1; // 返回不重复序列的长度
}

说明:

  • 与Java版本逻辑相同,只是语法有所不同。
Python3版本
def removeDuplicates(nums):
    if not nums:
        return 0
    
    i = 0 # 慢指针,指向不重复序列的末尾
    for j in range(1, len(nums)): # 快指针,遍历数组
        if nums[j] != nums[i]:
            i += 1
            nums[i] = nums[j]
    
    return i + 1 # 返回不重复序列的长度

说明:

  • Python版本与Java和C版本逻辑相同,只是语法和习惯用法

有所不同。

复杂度分析

  • 时间复杂度:O(n),其中n是数组的长度。因为每个元素只被遍历一次。
  • 空间复杂度:O(1)。只使用了常数级别的额外空间。

方式二:使用集合(不适用于原地修改要求)

思路

将数组中的元素放入一个集合中,自动去重,然后再将集合中的元素放回数组。但这种方式不满足题目要求的原地修改和O(1)额外空间的要求,因此不推荐在实际题目中使用。

代码实现

Java版本
import java.util.LinkedHashSet;
import java.util.Set;
public int removeDuplicates(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    
    Set<Integer> set = new LinkedHashSet<>();
    for (int num : nums) {
        set.add(num);
    }
    
    int index = 0;
    for (int num : set) {
        nums[index++] = num;
    }
    
    return set.size();
}

说明:

  • 使用了LinkedHashSet来保持元素的插入顺序。
  • 遍历数组,将元素加入集合中自动去重。
  • 遍历集合,将元素放回数组。
  • 返回集合的大小,即去重后的数组长度。
C语言版本

由于C语言没有内置集合类型,实现起来相对复杂,需要手动实现哈希表或链表等数据结构,这里不给出C语言的集合实现方式。

Python3版本
def removeDuplicates(nums):
    if not nums:
        return 0
    
    nums[:] = list(dict.fromkeys(nums))
    return len(nums)

说明:

  • 利用Python的字典dict来自动去重,dict.fromkeys(nums)会创建一个以nums为键的字典,由于字典的键是唯一的,所以会自动去重。
  • 然后将字典的键转换回列表,并赋值给原数组nums
  • 返回列表的长度,即去重后的数组长度。

复杂度分析

  • 时间复杂度:O(n),其中n是数组的长度。遍历数组和集合操作都是线性的。
  • 空间复杂度:O(n)。使用了额外的集合来存储去重后的元素。

总结

方式 优点 缺点 时间复杂度 空间复杂度
方式一 原地修改,满足题目要求 代码稍微复杂一些 O(n) O(1)
方式二 代码简洁,易理解 不满足原地修改和O(1)额外空间的要求 O(n) O(n)

相似题目

相似题目 难度 链接
27. 移除元素 简单 力扣-27
80. 删除有序数组中的重复项 II 中等 力扣-80
268. 缺失数字 简单 力扣-268

这些题目都与数组操作、去重和移除元素有关,可以通过练习这些题目来加深对数组操作的理解

相关文章
|
1月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
69 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
5天前
|
机器学习/深度学习 人工智能 算法
基于Python深度学习的【垃圾识别系统】实现~TensorFlow+人工智能+算法网络
垃圾识别分类系统。本系统采用Python作为主要编程语言,通过收集了5种常见的垃圾数据集('塑料', '玻璃', '纸张', '纸板', '金属'),然后基于TensorFlow搭建卷积神经网络算法模型,通过对图像数据集进行多轮迭代训练,最后得到一个识别精度较高的模型文件。然后使用Django搭建Web网页端可视化操作界面,实现用户在网页端上传一张垃圾图片识别其名称。
26 0
基于Python深度学习的【垃圾识别系统】实现~TensorFlow+人工智能+算法网络
|
5天前
|
机器学习/深度学习 人工智能 算法
【手写数字识别】Python+深度学习+机器学习+人工智能+TensorFlow+算法模型
手写数字识别系统,使用Python作为主要开发语言,基于深度学习TensorFlow框架,搭建卷积神经网络算法。并通过对数据集进行训练,最后得到一个识别精度较高的模型。并基于Flask框架,开发网页端操作平台,实现用户上传一张图片识别其名称。
21 0
【手写数字识别】Python+深度学习+机器学习+人工智能+TensorFlow+算法模型
|
5天前
|
机器学习/深度学习 人工智能 算法
基于深度学习的【蔬菜识别】系统实现~Python+人工智能+TensorFlow+算法模型
蔬菜识别系统,本系统使用Python作为主要编程语言,通过收集了8种常见的蔬菜图像数据集('土豆', '大白菜', '大葱', '莲藕', '菠菜', '西红柿', '韭菜', '黄瓜'),然后基于TensorFlow搭建卷积神经网络算法模型,通过多轮迭代训练最后得到一个识别精度较高的模型文件。在使用Django开发web网页端操作界面,实现用户上传一张蔬菜图片识别其名称。
25 0
基于深度学习的【蔬菜识别】系统实现~Python+人工智能+TensorFlow+算法模型
|
10天前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
|
10天前
|
算法 Python
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
28 2
|
1月前
|
存储 机器学习/深度学习 算法
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
蓝桥杯Python编程练习题的集合,涵盖了从基础到提高的多个算法题目及其解答。
60 3
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
|
22天前
|
机器学习/深度学习 人工智能 算法
【车辆车型识别】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+算法模型
车辆车型识别,使用Python作为主要编程语言,通过收集多种车辆车型图像数据集,然后基于TensorFlow搭建卷积网络算法模型,并对数据集进行训练,最后得到一个识别精度较高的模型文件。再基于Django搭建web网页端操作界面,实现用户上传一张车辆图片识别其类型。
65 0
【车辆车型识别】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+算法模型
|
26天前
|
机器学习/深度学习 算法 Java
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
|
1月前
|
算法
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
23 2