26. Remove Duplicates from Sorted Array

https://leetcode.com/problems/remove-duplicates-from-sorted-array/description/

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,

Given input array nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.

Thoughts

对给定数组压缩：将重复元素剔除。前后双指针，后指针每次前进一格并比较当前字符和后面是否一致（或到了最后一个字符），一致时跳过，否则在前指针位置开始替换。

Code

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        j = 0
        for i, num in enumerate(nums):
            if i == len(nums) - 1 or num != nums[i + 1]:
                nums[j] = nums[i]
                j += 1
        return j
        

class Solution {
    public int removeDuplicates(int[] nums) {
        int pos, i;
        for (i = 0, pos = 0; i < nums.length; i++) {
            if (i == nums.length - 1 || nums[i] != nums[i + 1]) {
                nums[pos++] = nums[i];
            }
        }

        return pos;
    }
}

Analysis

时间复杂度O(n), 空间O(1).