Leecode - 从数组中删除重复项

kamushin233 发布于2019-08-23 18:04 / 647人阅读

摘要：原文地址题目给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。示例给定函数应该返回新的长度并且原数组的前五个元素被修改为。

原文地址: https://www.luoyangfu.com/art...

题目

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

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 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]);
}

思路

根据题目说明:

排序的数组 -> 数组是有序的

原地删除重复数组 -> 不能移除

每个元素只出现一次 -> 时间复杂度O(n)

不能使用额外的数组空间 -> 不能复制元素

不用考虑数组中超出长度的数据 -> 和第2条对应，把要移除的元素放到后面

我们需要在 时间复杂度为O(n) 情况下为一个有序的数组做一个删除，我们使用一个计数变量 i = 0 来标记当前数组不重复的数据的，但是这个时候我们需要 原地删除 数组，这个时候就需要重复的数据放到后面，这样返回的数据就可以保持在前面 i 个数据是不重复的。既然需要和后面元素交换，数组交换需要两个下表，我们这里再采用另外一个 计数变量j 来表示作为当前数组遍历计数变量. 根据上述描述，我们使用的方法也称之为双指针法. 这里i 称之为慢指针， j 称之为快指针

双指针，顾名思义，就是利用两个指针去遍历数组，一般来说，遍历数组采用的是单指针（index）去遍历，两个指针一般是在有序数组中使用，一个放首，一个放尾，同时向中间遍历，直到两个指针相交，完成遍历，时间复杂度也是O(n)。

解决方法

根据解决思路我们这里使用 javascript 语法来开发:

function removeDuplicates(arr) {
    
    if(!Array.isArray(nums) || !nums.length) return 0;
  
    if(nums.length < 2) return 1;
    
    var i = 0;

    for(var j = 1; j < nums.length; j ++) {
    
        if(nums[i] !== nums[j]) {
            i ++; 
            nums[i] = nums[j]
        }
    }
    
    return ++i;
}

上面代码有两点要解释的，判断 nums[i] !== nums[j] 这里，当他们不相等的时候进行 i 和 j 的位置交换, 当相同的时候j 就跳过相同的元素的， i++ 就在不同的下一个元素进行交换。在最后返回 ++i 这里，以为 i 是从0开始，因此长度需要+1.

GPU云服务器云服务器数组重复项删除重复数组 js查找数组中重复的重复项

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/104625.html

Leecode-3 Longest Substring Without Repeating Char

摘要：题目解析题目含义很简单，即求出没有字符重复的子字符串的长度。例如很明显就是个由完全重复字符组成的字符串，所以它的答案长度为。所以综合来看该算法的效率为。题目 Given a string, find the length of the longest substring without repeating characters. Example 1: Input: abcabcbbO...

luzhuqun 2019-08-16 13:49 评论0 收藏0
leecode 39 Combination Sum

摘要：我们需要找出中的数字的不同组合，使得每一种组合的元素加和为。输入的候选集和目标数字结果集是想法这道题采取了递归的思路。每次将一个元素加入的时候，判断是否满足中的元素加和等于，如果等于，直接将加入最终返回的结果集。题目详情 Given a set of candidate numbers (C) (without duplicates) and a target number (T),...

yhaolpz 2019-08-15 14:15 评论0 收藏0
[Leecode] Linked List Cycle 链表环

摘要：快慢指针法复杂度时间空间思路这是一道非常经典的双指针题。如果快指针和慢指针相遇，则说明链表有环。代码快慢指针法复杂度时间空间思路这题是基于上一题，上一题我们发现相遇后就返回了，而这里我们还要继续找到环的起始点。 Linked List Cycle I Given a linked list, determine if it has a cycle in it.Follow up: Ca...

includecmath 2019-08-14 12:27 评论0 收藏0
LeetCode-Remove Element-从排序数组中删除重复项

摘要：描述给定一个有序数组，你需要原地删除其中的重复内容，使每个元素只出现一次并返回新的长度。最后慢指针指向的元素及前面所有元素都是不重复的。描述：给定一个有序数组，你需要原地删除其中的重复内容，使每个元素只出现一次,并返回新的长度。不要另外定义一个数组，您必须通过用 O(1) 额外内存原地修改输入的数组来做到这一点。示例：给定数组: nums = [1,1,2], 你的函数应该返回新...

dayday_up 2019-07-30 16:07 评论0 收藏0
【刷算法】LeetCode.26-从排序数组中删除重复项

摘要：题目描述给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。示例给定函数应该返回新的长度并且原数组的前五个元素被修改为。也就是说，不对实参做任何拷贝在函数里修改输入数组对于调用者是可见的。题目描述给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输...

wua_wua2012 2019-08-23 11:45 评论0 收藏0