[리트코드] 26. Remove Duplicates from Sorted Array

문제

https://leetcode.com/problems/remove-duplicates-from-sorted-array/?envType=study-plan-v2&envId=top-interview-150 

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

 

---

✔ 문제접근 #1 순차탐색[통과] ⭕

Intuition
주어진 배열은 오름차순으로 정렬되어 있다. 중복되는 수가 연속적으로 나타나 있을 것이다.

전체 요소를 순회하며 현재 값이 이전 값과 서로 다른 경우 앞에서부터 채워준다.

Algorithm

nums에 마지막으로 삽입된 위치 idx를 선언한다. 전체 nums의 요소를 순회하며 idx위치에 있는 값과 서로 다르다면 idx + 1의 위치(다음위치)에 순회한 요소 nums [i]를 넣는다.

 

결과과적으로 nums 배열의 앞에서부터 idx + 1개의 데이터가 고유한 값으로 채워지게 된다.

    def removeDuplicates(self, nums: List[int]) -> int:
        
        idx = 0
        for i in range(len(nums)):
            if nums[idx] != nums[i]:
                idx += 1
                nums[idx] = nums[i]

        return idx + 1

 

Complexity Analysis

• 시간 복잡도 : O(N)
  • num 배열을 순차탐색 O(M)
  • 그러므로 전체시작복잡도 : O(N)

• 공간복잡도 : O(1)
  
  • 기존의 num 배열을 재사용하기 때문에 추가적인 메모리를 사용하지 않는다.

---

기타 풀이 및 회고

기존 배열을 그대로 사용하기 때문에 in-place방식으로 추가적인 메모리를 사용하지 않았다.

또 다른 풀이로는 set자료구조를 사용하는 것이다. 내부적으로 중복되는 값을 허용하지 않기 때문에 set자료구조를 활용하여 중복을 제거한 후, 원래의 nums배열에 담아주면 된다.