[Two Pointers] 26. Remove Duplicates from Sorted Array

26. Remove Duplicates from Sorted Array

 

https://leetcode.com/problems/remove-duplicates-from-sorted-array/description/

 

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        left, right = 0, 0
        while right < len(nums):
            if nums[left] == nums[right]:
                right +=1
            elif nums[left] < nums[right]:
                left += 1
                nums[left] = nums[right]
        print(nums)
        return left+1

 

주의 할 점

 

바로 return left 대신 return left + 1을 해줘야 해요.

이유:

• left는 마지막 고유한 원소의 인덱스이고, 문제는 고유한 원소의 개수 k를 반환하라고 했죠.
• 예를 들어 고유한 값이 5개면, 인덱스는 0부터 4까지니까 left = 4가 되는데, 실제 고유한 개수는 left + 1 = 5여야 해요.

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

 

핵심 요약:

• left는 고유한 값이 들어갈 위치를 가리킴
• nums[right] != nums[left]일 때만 left를 한 칸 옮기고, 그 자리에 nums[right]를 덮어씀
• 마지막에 left + 1을 리턴해야 고유한 숫자의 개수가 됨

 

https://youtu.be/DEJAZBq0FDA

 

최종 풀이

 

해시맵으로..

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        hashmap = {}
        for n in nums:
            if n in hashmap:
                hashmap[n]+=1
            else:
                hashmap[n]=1
        for i, (k, v) in enumerate(hashmap.items()):
            nums[i] = k
        return len(hashmap)

 

투 포인터로..

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0

        left = 0
        for right in range(1, len(nums)): # for right in range(len(nums)): 
            if nums[left] != nums[right]: # nums[left] < nums[right]:
                left += 1
                nums[left] = nums[right]
        #print(nums)
        return left+1

 

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        l, r = 0, 1
        while r<len(nums):
            if nums[l] != nums[r]:
               l +=1
               nums[l] = nums[r]
            
            r+=1 
        # print(nums, l, r)
        return l+1 # index 가 0부터 시작하므로, +1 해줘야 함

Time & Space Complexity

• Time complexity: O(n)
• Space complexity: O(1)

 

dd

 

ff