26. Remove Duplicates from Sorted Array

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

2. Example

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

3. Solution

• Runtime: 0ms
• 📌이 문제를 풀 때 리스트를 하나 더 만들어 거기에 값을 저장하는 것이 아닌 하나의 리트에서 삭제를 해야하니 어쩔 줄 몰랐다. 그래서 결국 제한 시간 30분을 쏘고도 못풀게 되어 블로그에 있는 답을 보고 Chat GPT로 코드 개선하여 이해하였다.
• 📌Chat GPT는 Two Pointers를 사용하여 알려주었다.
• 설명
  • 리스트가 비어있을 경우를 확인하고 0을 return한다.
  • nums리스트를 인덱스 1부터 시작한다.
  • nums[i]와 nums[cnt-1]이 다를시 (중복이 아닌 경우) nums[cnt] = nums[i]로 지정한다.
    • cnt는 중복이 아닌 경우에 1씩 더한다.
    • 이를 통해 nums[0]는 저장하고 그다음 cnt = 1이니까 nums[1]부터 중복이 아닌 값을 지정해준다고 생각하면 된다.
  • cnt는 결국 k값을 의미한다.

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

• ✏️Two Pointers (투 포인터)
  • 두 개의 포인터(변수)를 사용하여 배열이나 리스트를 탐색하는 알고리즘 기법이다.
  • 정렬된 배열이나 연속된 부분 배열을 다룰 때 유용하다.
• 유형
  1. 같은 방향으로 이동하는 투 포인터
     • 배열을 순차적으로 탐색하면서 특정 조건을 만족하는 요소를 찾음
     • i,cnt 같은 방향으로 움직이며 배열 탐색
     • 예시
       • 정렬된 배열에서 중복 제거
       • 연속된 부분합 구하기
  2. 양쪽 끝에서 시작하는 투 포인터
     • 배열의 양 끝에서 시작해 중앙으로 이동하면서 특정 조건을 만족하는 요소를 찾음
     • left, right 양 끝에서 시작하여 중앙으로 이동

4. What I Learned

References

• LeetCode 26. Remove Duplicates from Sorted Array 정답풀이
• Chat GPT