 1

 80

LeetCode天梯🏆0001:从排序数组中删除重复项

唐羲

2019-12-24 21:49:30

【数组】从排序数组中删除重复项

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

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

示例:

给定数组 nums = [1,1,2], 

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 

你不需要考虑数组中超出新长度后面的元素。

示例:

给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。

开始解题

  • 思路一

既然是在原排好序的数组上删除重复出现的数字,返回移除重复数字后的新数组长度,联系到 JavaScript 中对数组的操作方法,自然而然想到 splice 方法,这个方法可以用来移除元素或添加元素,并且会破坏原数组,正好切题。

然后,既然是排好序的数组,那重复的数字只可能出现在相邻的两个数上,那么进行循环,将数组的相邻元素比较,如果 nums[i] === nums[i+1],则移除 nums[i],此时数组长度会减去 1,而下一次循环 i 值会加 1,导致取数不准备,所以需要将 i 值减 1。不相等的情况说明不是重复的,则不用管。这样只执行了一次循环,复杂度为 O(n)。

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    for (var i = 0; i < nums.length; i++) {
        if (nums[i] === nums[i+1]) {
            nums.splice(i, 1)
            i--
        }
    }
    return nums.length
};

在 LeetCode 中提交通过后,便去看了下这个算法的耗时排名,居然还有比这更快的,复杂度感觉没办法降低了,只能说从性能损耗方面思考了,splice 操作肯定是有比较“大”性能耗损的,所以有了思路二。

  • 思路二
/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    let len = 1
    for(let i = 1; i < nums.length; i++) {
        if(nums[i] !== nums[i - 1]) {
            nums[len++] = nums[i]
        }
    }
    return len
}

发表评论

登陆 后发表评论

评论列表

还没有评论,快来做第一个评论的人吧