Skip to content

26. 删除排序数组中的重复项 #4

Description

@Geekhyt

原题链接

双指针

题目要求原地删除重复出现的元素,不要使用额外的数组空间,返回移除后数组的新长度。

先明确,这道题给我们提供的是排好序的数组,所以重复的元素必然相邻。

所以实际上我们只需要将不重复的元素移到数组的左侧,并返回其对应的长度即可。

1.借助双指针,i 从索引 0 开始,j 从索引 1 开始。
2.当前项 nums[j] 与前一位置 nums[j - 1] 相等时,j++ 跳过重复项。
3.当二者不相等时,意味着不是重复项,此时需要将 i 指针右移, 并将 nums[j] 复制到此时的 nums[i] 位置上,然后将指针 j 右移。
4.重复上述过程,直到循环完成,最终返回 i + 1,因为题目要求返回长度,i 是索引位置,加 1 即所求。

const removeDuplicates = function(nums) {
    const n = nums.length
    let i = 0
    if (n === 0) return 0
    for (let j = 1; j < n; j++) {
        if (nums[j] !== nums[j - 1]) {
            i++
            nums[i] = nums[j]
        }
    }
    return i + 1
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions