5. Remove Duplicates from Sorted Array

문제

정렬된 배열 nums 에서 중복되는 요소 삭제.

추가 배열 생성하지 말고 in-place로 해결할 것.

남은 요소 개수 k 반환

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]

 

내가 생각한 방식(c++)

i는 0에서 시작, j가 가리키는 요소를 한 칸씩 채우면서 앞으로 가는 포인터
j도 0에서 시작,  유일한 요소를 가리키는 포인터

=> 인풋이 [1, 2, 2, 3]인 경우 아웃풋이 [1, 2, 3]으로 맞음

=> 인풋이 [1, 2, 2]인 경우 아웃풋이 [1, 2, 2], k=3으로 틀림

int removeDuplicates(int* nums, int numsSize){
    // i는 한 칸씩 채우면서 앞으로 가는 포인터
    // j는 유일한 요소를 가리키는 포인터
    int i = 0;
    int j = 0;
    int count = 1;

    while(i < numsSize && j < numsSize){
        // i가 유일한 요소를 가리키는 경우
        if (nums[i] != nums[i+1]){
            nums[i++] = nums[j++];
            count++;
        } else {
            // i가 중복되는 경우
            // j가 다음 유일한 요소 가리키게 만들기
            while (nums[j] == nums[i] && j < numsSize - 1){
                j++;
            }
            nums[i+1] = nums[j++];
            count++;
            i += 2;
        }
    }
    return count;
}

 

해결책(python)

https://leetcode.com/problems/remove-duplicates-from-sorted-array/discuss/2107606/Python-All-4-Methods%3A-Intuitions-Walk-through-Wrong-answer-explanations-for-Begninners

i는 한 칸씩 앞으로 가며 탐색하는 포인터. 인덱스 1에서 시작

j는 중복 요소를 가리키는 포인터. 인덱스 0에서 시작

 

i요소와 j요소가 같으면 i만 증가.

i요소와 j요소가 다르면

   - j를 1 증가.

   - j 요소를 i요소로 변경

def removeDuplicates(self, nums: List[int]) -> int:
    j = 0

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

    return j + 1