26. Remove Duplicates from Sorted Array

今天我们一起挑战leetcode第26题Remove Duplicates from Sorted Array！

题目

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
If all assertions pass, then your solution will be accepted.

Example 1:
Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,,,,,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

这个题目叙述真的是有点长，我们简单来说的话，其实这题目就是会给我们一个排序过的阵列，希望我们把阵列重复的元素拿掉。但这题是不用回传阵列的，只要在原本的阵列把移除重复元素後的阵列，所有元素往阵列头的方向排，然後再回传一整数来表示在阵列中有几个不重复的数字。

这题有额外要求，不可以另外新增O(n)的空间，必须在复杂度O(1)达成，且题目也不会管不重复元素後的元素是放麽东西，也就是他只会检查阵列中的前K（不重复元素个数）个。

Forloop

我们可以利用题目本身的阵列一定是排序过的特性来做这道题目，额外利用两个变数来记住现在要放的位置（count）和现在已经看过的值，概念上是只要我们没有看过的东西我们就把他放到阵列index为0的位置，而此时count就加一，下次再看到新的东西时就会放到index为1的位置。这边的放到某个位置是指直接改变那个位置的值不是插入，如此一来，只需要遍历回圈一遍就能成功达到题目的要求。在程序码中我也会用comment来说明概念，如果还是不太清楚可以直接看一下code。

以下是python3的程序码

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0  # 空阵列就回传0
        compare = nums[0] # 把第一个元素当作基准
        count = 1  # 因为非空阵列至少为一
        for i in range(1, len(nums)):  # 从index1开始
            if nums[i] != compare:   # 如果比对到不同的
                nums[count] = nums[i]  # 就放对对应的位置
                compare = nums[i]  # 更改比对基准
                count += 1  # 计数器加一
        return count

以下是C++的程序码

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.empty()){
            return 0;
        }
        int count=1;
        int compare=nums[0];
        for(int i=1;i<nums.size();i++){
            if(nums[i] != compare){
                nums[count] = nums[i];
                compare = nums[i];
                count++;
            }
        }
        return count;
    }
};