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.

 

 

 

풀이

처음에는 딕셔너리나 리스트를 통해서 방문리스트를 만든 후 카운트를 넘는다면 수를 제외하고 새로운 인덱스에 넣어서 

nums리스트를 모두 비우고 넣는 방식을 생각했었다.

 

하지만 문제에서 새로운 배열을 만드며 메모리를 사용하지말라는 조건 떄문에 다른 방법을 생각했다.

 

이전의 문제에서 투포인터로 문제를 풀었었고 다른 사람의 코드를 보며 좀 더 깔끔하게 짤 수 있다는 사실을 알고 

투포인터를 통해서 문제를 풀어봤다. 기존에 풀었던 코드는 위치 포인터와 새로운 값을 지정하는 변수등이 많아서 보기 지저분했는데  이번에 짠 코드는 좀 더 직관적인거 같다.  

 

포인터를 시작과 끝에 두지 않고 일정 기준에 충족하는 값인지 확인한 후 앞으로 증가해나가는 방식으로 푼건 처음인거같다. 

class Solution(object):
    def removeDuplicates(self, nums):
        cnt = 1 # 체크를 1번 인덱스부터 하는게아니라 0번인덱스부터 시작 [0] ,[1] 인덱스부터 체크하기에 미리 cnt=1로 지정
        index =0  #숫자를 넣어줄 포인터(인덱스포인터)
        for i in range(1,len(nums)): # for문으로 1번부터 원소 끝까지 체크
            if nums[i] != nums[index]: # 인덱스 포인터와 지금 현재 위치의 수가 다르다면 
                cnt=1       		  # 동일한 숫자가 아니라면 새로운 숫자, 횟수 1번 카운트
                index+=1              # 인덱스 번호 +1 (이미 전의 인덱스는 옳게 배치되어있음)
                nums[index]=nums[i]   # 인덱스포인터가 가르키는 위치에 현재 숫자로 변경
            elif nums[i] == nums[index] and cnt<2: # 두 포인터 인덱스 수가 같고 count된 수가 2 이내라면 
                cnt+=1				  # 같은 수 체크 횟수 증가
                index+=1			  # 인덱스포인터 +1 증가
                nums[index]=nums[i]   # 인덱스포인터의 위치의 숫자를 현재위치의 수로 변경
        return index+1                # index포인터가 끝나는 위치 체크 
 
 
 #sudo
 
 class Solution(object):
    def removeDuplicates(self, nums):
        cnt =  동일한 숫자가 나온 횟수
        index = nums에 지정해줄 인덱스의 위치 
        for i in range(배열의 두번째수부터 끝번수 ): 
        	if nums[i] != nums[index]: 두 수가 다르다면 index의 위치에 숫자를 변경
                cnt = 최초발견 카운트 1로 지정
                index+= 위치 +1 증가 ( 기존값이 옳은값인걸 확인가능)
                nums[index]=nums[i]   
            elif nums[i] == nums[index] and cnt<2:  # 두 수가 다르지만, 카운트가 한번이라면
                cnt+=1				  #위의 코드 반복 
                index+=1			  
                nums[index]=nums[i]   
                
        return index+1 #새로 배정된 수의 끝번 체크 , 인덱스를 넘어가는 원소는 버리는 원소

 

 

제일 투표를 많이 받은 python코드 

def removeDuplicates(self, nums):
    i = 0
    for n in nums:
        if i < 2 or n > nums[i-2]: #문제에서 동일한 수가 2개까지 가능하므로 3번째인덱스부터 체크,
        							#현재 위치에서 -2번쨰 숫자보다 크다면 
            nums[i] = n				
            i += 1
    return i

직관적이고 이해하기 쉬운코드인거같다. 

처음엔 투포인터 코드를 보고 이해하기어려워서 파이썬튜터도 돌려봤었는데 이젠 조금 코드를 금방 이해하는거같다.

'알고리즘 > LeetCode' 카테고리의 다른 글

LeetCode 189. Rotate Array  (0) 2023.08.25
LeetCode 169. Majority Element  (0) 2023.08.25
LeetCode 26. Remove Duplicates from Sorted Array  (0) 2023.08.24
LeetCode 27. Remove Element  (0) 2023.08.24
LeetCode - 88. Merge Sorted Array  (0) 2023.08.23

+ Recent posts