[Leetcode] 26. Remove Duplicates from Sorted Array

Identifying the Problem

주어진 수열 내에 존재하는 중복 요소들을 제거하고, 수열의 길이를 리턴한다.

 

제한 조건은 다음과 같다.

• 0 <= 수열의 길이 <= 3 * 10^4
• -100 <= 개별요소 값 <= 100
• 주어진 수열은 오름차순이다.
• 시간복잡도 O(1)이고, 다른 수열을 생성해선 안된다. 

Organizing thoughts

Main idea는 중복된 수가 있을 때 마다 pass하고,

비교하는 두 수가 서로 다를 때, 더 큰 수를 앞에 보내면 된다.

즉, 다음 수를 누적중복된 만큼 앞으로 보내면 된다. (아래에서 누적중복은 pass의 개수이다.)

 

다음과 같이 이해하면 쉬울 것 같다.

nums	1	1	1	3	4	5
index	0	pass	pass	3->1	4->2	5->3

 

1. numSize 가 0,1 인 경우는 중복이 불가능하다.

2. 앞과 뒤를 비교하려면 size - 1 까지 해야한다.

3. 같을 경우 누적중복을 증가시키고,

4. 다를 경우 다음 수를 누적중복 앞만큼 보낸다. 

 

Sourcecode

int removeDuplicates(int* nums, int numsSize){
    int count = 1;
    int flag = 0;
    
    if(numsSize <2) return numsSize; //1
    
    
    for(int i =0;i<numsSize-1;i++) //2
    {
      if(nums[i] == nums[i+1]) //3
          flag ++;
      else
      {
        nums[i-flag+1] = nums[i+1]; //4
        count++;

      }
    }

    
    return count;
}

Mistake

처음에 중첩 반복문으로 작성했다가, 시간복잡도에서 벗어나서 컽 당했다.

도저히 모르겠어 로직을 참고했다.

New things learned

누적 중복 말고, 반복문 i 와 다른 속도로 가는 새로운 index 를 적용시키면 더 직관적일 것 같다.