大家好，我是毛毛。ヾ(´∀ ˋ)ﾉ
废话不多说开始今天的解题Day~

26. Remove Duplicates from Sorted Array

Question

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

Example1

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).

Example2

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).

Constraints

• 0 <= nums.length <= 3 * 104
• -100 <= nums[i] <= 100
• nums is sorted in non-decreasing order.

解题

题目

首先先简单的翻译一下题目
给定一个从小排到大排序的阵列，要用in-place的方式将阵列中重复的元素删除，使每个元素在阵列中只出现一次，并且每个元素的大小排序不变。
但是有些语言可能没办法改变阵列的长度，可以将不重复的k个元素放在阵列的前k个位址，而k+1之後的位址的内容评分程序并不会管。

最後的回传值是不重复的元素个数。

这题的限制是不能使用到额外的阵列。只能透过in-place的方式修改原来的阵列。

Think

由於in-place限制的关系，只能透过修改原来的阵列来处理。

作法大致上是这样

• 用index1和index2来指阵列的位址，比较是不是相同的，是的话就删掉它，不是的话index1和index2就加1，然後继续判断。
• Python跟C的写法虽然差不多，但C没办法更改阵列长度，所以这边我是把不重复的元素往前存，比到最後index1+1就代表的是不重复元素的数量；Python的话就用pop将重复的元素丢出阵列中，最後再回传阵列长度就好。

Code

Python

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        # 2 pointer for the nums array
        index1 = 0
        index2 = 1

        while(True):
            # ========================
            # * denotes index1.
            # @ denotes index2.
            #
            # Example: [0, 0, 1, 1, 2]
            #        *
            # Step1: 0 0 1 1 2
            #          @
            # => Value of * and @ are both 0. So we just need to pop value of @.
            #    Because of the feature of pop, the next element will fill in the value of @.
            #
            #        *
            # Step2: 0 1 1 2
            #          @
            # => The position of the 2 pointer are the same. We just need to compare them again.
            #    As shown in Step2, value of * and @ are different. So, both * and @ should plus 1.
            #
            #          *
            # Step3: 0 1 1 2
            #            @
            # => The same situation in Step1.
            #
            #          *
            # Step4: 0 1 2
            #            @
            # => As @ equals to length of array, the for loop will be break.
            #    We just need to return the length of array.
            # ========================

            # exception processing
            if len(nums) <= 1:
                return len(nums)

            if nums[index1] == nums[index2]:
                nums.pop(index2)
            else:
                index1 += 1
                index2 += 1

            if index2 == len(nums):
                break

        return len(nums)

C

int removeDuplicates(int* nums, int numsSize){
    int index1 = 0;
    int index2 = 1;

    if(numsSize <= 1){
        return numsSize;
    }

    while(true){
        if(nums[index1] == nums[index2]){
            // Exception => ex: [1,1]
            if(index2 == (numsSize-1)){
                return (index1+1);
            }
            index2++;

        } else {
            index1++;
            nums[index1] = nums[index2];

            if(index2 == (numsSize-1)) return (index1+1);
            else index2++;

        }
    }
}

Result

• Python

  • 

• C

  • 

大家明天见