[LeetCode] Remove Duplicates from Sorted Array

목차

문제

• 오름차순으로 정렬된 nums 배열에서 중복된 값들을 제외한 값들의 개수를 구하는 문제입니다.
• 예시

  • Input: nums = [1,1,2]
    Output: 2, nums = [1,2,_]

  • Input: nums = [0,0,1,1,1,2,2,3,3,4]
    Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]

• 제약사항
• • 1 <= nums.length <= 3 * 104
  • -100 <= nums[i] <= 100
  • nums is sorted in non-decreasing order.

문제 풀이

풀이 1 : Two indexes approach

• 풀이
  • 특정 배열의 첫번째값은 무조건 있어야 합니다. 따라서 i는 1부터 시작하고, j 역시 1부터 n까지 진행됩니다.
  • 이때 이제 arr[j-1]!=arr[j] 일 경우 전에 값과 다른 경우이기 때문에 arr[i] = arr[j]로 변경시켜주어야 합니다. 그리고 i번째 값이 채워졌기 때문에 i+=1을 해줍니다.
• 코드

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

• 시간복잡도
  • O(n)

알게 된 내용

• 정렬된 배열에서 중복된 값들을 제거할 때 위 코드를 사용하면 효율적으로 제거가 가능합니다.

출처

• https://leetcode.com/explore/learn/card/fun-with-arrays/526/deleting-items-from-an-array/3248/