[리스트] Leet Code 26. Remove Duplicates from Sorted Array

 

리스트에서 중복값을 제외하고

중복값 제외한 숫자들의 개수를 구한다.

 

 

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

시간복잡도

O(N^2) : len(nums)만큼 쭈욱 탐색하면서 O(N) -> pop(i) O(N)   ([1,1,1,1,1] 인 경우)

 

공간복잡도

O(1) : 변수 i 공간 1개만 필요

 

 

솔루션 보고 개선한 코드

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

중복되지 않는 값들을 앞에다가 놓는다.

i 인덱스는 박힌돌, j인덱스는 굴러들어온 돌

박힌돌과 다른 값을 가진 굴러들어온 돌이 있을 때 박힌돌 다음번째(i+=1)값을 굴러들어온 돌 값으로 바꿔치기 한다.

 

시간복잡도

O(N) : len(nums)만큼 쭈욱 탐색하면서 중복일 때 swap

 

공간복잡도

O(1) : 변수 i 공간 1개 O(1) + 변수 j 공간 1개 O(1)