Remove Duplicates from Sorted Array(E)

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

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. Then return the number of unique elements in nums.

Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:

• Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.
• Return k.

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

 

Constraints:

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

1. Python 만만돌이다

 

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if nums == [] : return 0;

        cnt = 1
        a = nums[0]
        lst = [a]

        for i in range(len(nums)):
            if nums[i] == a:
                continue
            a = nums[i]
            cnt +=1
            lst.append(a)

        for j in range(cnt):
            nums[j] = lst[j]

        return cnt

하고보니  투박했던 나으 코딩..

 

GPT는 좀 더 깔끔하게 한다. using 2 pointer

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums : return

        ptr = 1

        for i in range(1,len(nums)) :
            if nums[i] != nums[i-1]:
                nums[ptr] = nums[i]
                ptr += 1
                
        return ptr

 

 

2. C

 

파이썬 GPT 답안을 괜히 봤다.

같은 메카니즘이 C에도 적용되는 사례!

int removeDuplicates(int* nums, int numsSize) {
    if(nums == NULL) return 0;

    int cnt = 1;

    for(int i=1;i<numsSize;i++){
        if(nums[i] != nums[i-1]){
            nums[cnt] = nums[i];
            cnt++;
        }
    }
    return cnt;

 

 

3. C++

 

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.empty()) return 0;

        int ans = 1;
        int temp = nums[0];

        for(int x : nums){
            if(x==temp){
                continue;
            }else{
                temp = x;
                nums[ans] = temp;
                ans++;
            }
            
        }
        return ans;
    }
};

 

답지가 무서운게 한 번 보면 뭔가 거기에 overfit 된다.

 

코딩실습할 때에는 답지를 호환마마로 여겨야겠다..!

 

그래도 10분 정도 빡시게 고민해보고 답 안 나오면 답지 보고 유형 익히는 게 효율면에선 좋을듯!