LeetCode | 26. 删除排序数组中的重复项

[aermin]

题目

解法

双指针法

数组完成排序后, 放一个i当慢指针，一个j当快指针，i初始值为0, j初始值为1；

用j快指针去循环遍历数组nums，因为要把不重复的值挑出来前置，所以当nums[j] !== nums[i] 的时候此时慢指针i加一，并该位置取快指针j的值，即nums[++i] = nums[j]。否则当nums[j] === nums[i]时，前面已有这个数，不用前置了直接跳过

注意：js中，nums[++i] 和nums[i++]不同，++i是在此计算语句中先执行，i++是在计算语句运行后再执行

const removeDuplicates = function(nums) {
    const length = nums.length;
    if(length < 2) return;
    let i = 0;
    for(let j = 1; j < length; j++) {
        if(nums[i] !== nums[j]) {
            nums[++i] = nums[j];
        }
    }
    return i+1;
};

复杂度分析

时间复杂度：O(n)，假设数组的长度是 n，那么 i 和 j 分别最多遍历 n 步。

空间复杂度：O(1)。

reference

题解