LeetCode.026.Remove Duplicates from Sorted Array 删除有序数组中的重复项

题目描述

026 Remove Duplicates from Sorted Array
https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
https://leetcode.com/problems/remove-duplicates-from-sorted-array/description/

Given a sorted array nums, 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 by modifying the input array in-place with O(1) extra memory.

Example 1:

Given 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 returned length.

Example 2:

Given nums = [0,0,1,1,1,2,2,3,3,4],
Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.
It doesn't matter what values are set beyond the returned length.

---

解题过程

相似题目
LeetCode.283.Move Zeroes 将数组中的零移到末尾
LeetCode.027.Remove Element 从数组中移除指定元素
LeetCode.026.Remove Duplicates from Sorted Array 删除有序数组中的重复项
LeetCode.080.Remove Duplicates from Sorted Array II 删除有序数组中的重复项2

原地移除有序数组中的重复元素。题目要求不得额外申请新数组，但超过新数组长度的元素不做要求。
使用快慢双指针：慢指针slow和快指针fast都从前往后扫描，快指针遇到非重复元素就赋值给慢指针、遇到重复元素就跳过，保证慢指针slow之前都是要保留的唯一元素。
时间复杂度 O(n)，空间复杂度 O(1)

SolutionV2018

private static class SolutionV2018 {
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int slow = 0, fast = 0;
        for (; fast < nums.length - 1; ) {
            if (nums[fast] != nums[fast + 1]) {
                nums[slow++] = nums[fast++];
            } else {
                fast++;
            }
        }
        nums[slow++] = nums[fast];
        return slow;
    }
}

我的方法是保留连续重复元素的最后一个（所以数组最后一个元素肯定要保留），看别人都是保留连续重复元素的第一个（所以数组第一个元素肯定要保留），比如：

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

        return count;
    }
}

SolutionV2020

private static class SolutionV2020 {
    public int removeDuplicates(int[] nums) {
        if (null == nums) {
            return 0;
        }
        if (nums.length < 2) {
            return nums.length;
        }
        int left = 0;
        for (int right = 1; right < nums.length; right++) {
            if (nums[right - 1] != nums[right]) {
                nums[++left] = nums[right];
            }
        }
        return left + 1;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_026_RemoveDuplicatesFromSortedArray.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_026_RemoveDuplicatesFromSortedArray.java

---