Question
Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.
Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.
Return k after placing the final result in the first k slots of nums.
Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.
Constraints:
- 1 <= nums.length <= 3 * 10^4
- -10^4 <= nums[i] <= 10^4
- nums is sorted in non-decreasing order.
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:한 리스트nums를 받아서 중복되는 원소를 2개까지만 허용하여 in-place로 해결하는 문제입니다. 이후 조건에 맞게 삭제된 이후의 리스트 길이를 반환합니다.
제가 생각한 코드는 다음과 같습니다.
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
idx,one_more = 0,True
for n in nums[1:]:
if nums[idx] != n:
one_more = True
elif one_more:
one_more = False
else:
continue
idx+=1
nums[idx] = n
return idx+1
idx:nums의 원소를 저장할 인덱스.one_more: 마지막으로 저장된 원소가 한번 더 저장이 가능한지 확인하는 boolean 변수nums의 두번째 원소를 시점으로 순회하면서nums[idx]와 비교합니다.- 새로운 원소가 나타난다면 해당 원소가 한 번 더 저장될 수 있으므로
one_more=True를 해줍니다. - 새로운 원소가 아니지만
one_more값이True라면one_more=False를 해줍니다. 이후 코드에서 값을 저장할 예정이기 때문입니다. - 새로운 원소도 아니고
one_more값도False라면 곧바로 다음 원소로 넘어갑니다. - 곧바로 넘어간 경우가 아니라면
idx값을 올리고 해당 원소를 저장합니다. idx는 최종적으로 마지막으로 저장된 인덱스 값을 가집니다. 리스트의 길이를 반환해야 하므로idx+1을 반환합니다.
2번 넘게 나온 원소가 아니라면 저장하는 방식으로 작성한 코드입니다.
