[leetCode] 80. Remove Duplicates from Sorted Array II (Python)

Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice 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.

Clarification:

Confused why the returned value is an integer, but your answer is an array?

Note that the input array is passed in by reference, which means a modification to the input array will be known to the caller.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy) int len = removeDuplicates(nums); // any modification to nums in your function would be known by the caller. // using the length returned by your function, it prints the first len elements. for (int i = 0; i < len; i++) {     print(nums[i]); }

 

Example 1:

Input: nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3]
Explanation: Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively. It doesn't matter what you leave beyond the returned length.

Example 2:

Input: nums = [0,0,1,1,1,1,2,3,3]
Output: 7, nums = [0,0,1,1,2,3,3]
Explanation: Your function should return length = 7, with the first seven elements of nums being modified to 0, 0, 1, 1, 2, 3 and 3 respectively. It doesn't matter what values are set beyond the returned length.

 

Constraints:

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

Solution

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        index = 0
        
        for num in nums:
            if index < 2 or num != nums[index-2]:
                nums[index] = num
                index = index + 1
                
        return index

Solution 풀이

오름차순으로 정렬되어있는 배열에서 2개이상 중복되는 수가 존재할 경우 중복된 수를 in-place 로 없애는 방법을 구현하는 문제입니다.

index면서 output으로 length를 담당할 변수 ( index )를 하나 선언합니다.

nums에서 숫자 ( num )를 하나씩 꺼냅니다.

만약 index의 값이 0이나 1일 경우 여기까지는 같은 숫자가 존재해도 전혀 문제가 되지 않으므로

nums의 index의 위치에 num을 그대로 넣어줍니다.

그 외의 3번째 부터는 숫자가 세번이상 반복되는지 확인하기 위해 현재 nums에서 나온 num과 nums배열의 index-2번째

즉, 현재 index보다 두 번 전에 존재하는 배열의 값을 비교하여 같지 않은 경우에만 index의 위치에 넣어주도록 합니다.

이 과정마다 계속 index의 값은 1씩 증가하여 최종적으로 index의 값은 최종적으로 중복을 제거한 배열의 길이값이 됩니다.

마지막으로 index값을 return하면 끝!

SOMJANG/CODINGTEST_PRACTICE