【力扣】 删除有序数组中的重复项 双指针解题

简介: 删除有序数组中的重复项 双指针解题

题目描述


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


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


将最终结果插入 nums 的前 k 个位置后返回 k 。


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


判题标准:


系统会用下面的代码来测试你的题解:


int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案
int k = removeDuplicates(nums); // 调用
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[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 已按 升序 排列

题目分析


因为之前解过链表的删除重复项问题:删除排序链表中的重复元素

再解答这道题就简单多了,我仍然采用双指针的思路解题


思路讲解


  1. 老规则,先做为空判断
  2. 既然是双指针,我们定义两个指针,一个命名为slow,一个命名为fast
  3. 循环快指针,如果快指针的相邻的元素不相等,则把当前指针赋值给慢指针
  4. 如果相等的话则说明是重复项,就不赋值给慢指针
  5. 最后我们输出慢指针,慢指针就是不包含重复项的有序数组了


AC代码


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


运行结果


微信图片_20221112165150.jpg


总结


复杂度分析


时间复杂度:O(n),其中 n 是数组的长度。快指针和慢指针最多各移动 n 次。

空间复杂度:O(1)。只需要使用常数的额外空间。

相关文章
|
1月前
leetCode(删除有序数组中的重复项)
如何在不使用额外空间的情况下,通过双指针法原地删除有序数组中的重复项。
32 2
|
3月前
|
存储 Java API
LeetCode------合并两个有序数组(4)【数组】
这篇文章介绍了LeetCode上的"合并两个有序数组"问题,并提供了三种解法:第一种是使用Java的Arrays.sort()方法直接对合并后的数组进行排序;第二种是使用辅助数组和双指针技术进行合并;第三种则是从后向前的双指针方法,避免了使用额外的辅助数组。
LeetCode------合并两个有序数组(4)【数组】
|
22天前
|
人工智能 自然语言处理 程序员
通义灵码:融合创新玩法与探索,重塑LeetCode解题策略
欢迎来到工程师令狐小哥的频道。本文介绍如何利用AI工具高效刷LeetCode,通过通义灵码插件在IntelliJ IDEA中实现代码生成、优化、单元测试等功能,提升编程学习效率。
57 1
通义灵码:融合创新玩法与探索,重塑LeetCode解题策略
|
30天前
【LeetCode 48】108.将有序数组转换为二叉搜索树
【LeetCode 48】108.将有序数组转换为二叉搜索树
34 0
|
3月前
|
算法
LeetCode第26题删除有序数组中的重复项
这篇文章介绍了LeetCode第26题"删除有序数组中的重复项"的解题方法,通过使用双指针技巧,高效地去除数组中的相邻重复元素。
LeetCode第26题删除有序数组中的重复项
|
3月前
|
算法
LeetCode第80题删除有序数组中的重复项 II
文章介绍了LeetCode第80题"删除有序数组中的重复项 II"的解法,利用双指针技术在O(1)空间复杂度内原地删除重复元素,并总结了双指针技术在处理有序数组问题中的应用。
LeetCode第80题删除有序数组中的重复项 II
|
3月前
|
算法
LeetCode第88题合并两个有序数组
文章分享了LeetCode第88题"合并两个有序数组"的解法,通过从后向前的合并策略避免了数组元素的前移,使用三个指针高效地完成了合并过程。
|
3月前
|
Python
【Leetcode刷题Python】108. 将有序数组转换为二叉搜索树
LeetCode上108号问题"将有序数组转换为二叉搜索树"的Python实现,通过递归选取数组中间值作为根节点,构建高度平衡的二叉搜索树。
25 2
|
3月前
|
算法 Java
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
54 0