[Leet Code풀이] 26. Remove Duplicates from Sorted Array

문제 설명

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

배열에서 중복값을 제거한후 남은 원소의 값을 리턴하는 문제

풀이

접근 방법. Two pointer

two pointer를 통해서 두개 인덱스를 조정해가면서 풀었다.

Approach, two pointer.
#0011122334
 ij         <- i, j 가 같으면 
 i j        <- j만 1칸더 올라감
#0011122334 <- 둘이 다르면
  ij        <- i를 한칸 올리고
#0101122334 <- 둘을 다꿈
  i j       <- j을 한칸더 올림
#0101122334 <- 둘을 다꿈
  i  j      <- i, j 가 같으면 j을 한칸더 올림
  i   j     <- i, j 가 다르므로
   i  j     <- i를 한칸 올리고
#0121102334 <- 둘을 바꿈
...         <- 이를 계속 반복

위 로직처럼 i와 j를 이동해가면서 처리하다보면 중복된 값이 제거된다.

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i = 0 
        j = 1
        cnt = 1
        while i < len(nums) and j < len(nums):
            if nums[i] == nums[j]:
                j += 1
            else:
                i += 1
                nums[i], nums[j] = nums[j], nums[i]
                j += 1
                cnt += 1
        return cnt 

위 풀이의 시간 복잡도와 공간복잡돈는 아래와 같다.

• 시간 복잡도 : O(N) nums만큼 루프를 도므로 O(N)

• 공간 복잡도 : O(1) 추가적인 공간을 사용하지 않는다.