LeetCode 26. Remove Duplicates from Sorted Array

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.

 

 

 

풀이법

 

처음엔 set을 사용해서 그대로 제출하려했지만 문제에서 원하는 자료구조 타입이 아니라 반려됬다.

 

그래서 그냥 nums의 원소를 다 비워버리고 set시킨 원소들로 다시 채워주는 법을 생각했다.

 

class Solution(object):
    def removeDuplicates(self, nums):
        set_nums = set(nums)
        for __ in range(len(nums)):
            nums.pop()
        for i in set_nums:
            nums.append(i)
        nums.sort()



#sudo

    def removeDuplicates(self, nums):
        set_nums = set(nums) #nums의 수를 set로 중복제거한다.
        for __ in range(len(nums)): nums의 원소를 모두 pop으로 비워준다.
            nums.pop()
        for i in set_nums: #set시킨 원소를 다시 넣어준다.
            nums.append(i)
        nums.sort()

 

 

1.set을 이용해서 문제를 푼 다른 사람의 코드 

방법 1: 다음을 사용하여 제자리 정렬[:]
	def removeDuplicates(self, nums: List[int]) -> int:
		nums[:] = sorted(set(nums))
		return len(nums)
시간 복잡도: O(n)
공간 복잡도: O(1)

❌ 일반적인 오답:
	nums = sorted(set(nums))
	return len(nums)
 nums =  원래 목록의 요소를 대체하지 않습니다.
nums[:] = 요소를 제자리에 대체합니다.

간단히 말해서, 없이 [:], 우리는 이 문제가 요구하는 것과 반대되는 새로운 목록 객체를 생성하고 있습니다:
"다른 배열에 추가 공간을 할당하지 마십시오. O(1을 사용하여 그 자리에서 입력 배열을 수정하여 이를 수행해야 합니다. ) 추가 메모리."

[:]를 통해서 제자리에서 정렬 할 수 있다는 사실을 처음알았다. 

 

 

2. 투포인터를 사용한 다른 사람의 코드 

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