大家好，我是毛毛。ヾ(´∀ ˋ)ﾉ
廢話不多說開始今天的解題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

  • 

大家明天見