[leetcode 26] Remove Duplicates from Sorted Array

Given a sorted array nums, remove the duplicates in-place such that each element appears only once and returns the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

 

정렬된 배열에서 중복된 수열을 제거한 요소가 앞에 오게 만들기. 그리고 중복된 요소를 제거한 길이를 return

0부터 len까지 배열을 print하므로 배열 변화가 반영된다.

 

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means a modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy) int len = removeDuplicates(nums); // any modification to nums in your function would be known by the caller. // using the length returned by your function, it prints the first len elements. for (int i = 0; i < len; i++) {     print(nums[i]); }

 

Example 1:

Input: nums = [1,1,2] Output: 2, nums = [1,2] Explanation: Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the returned length.

Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4] Output: 5, nums = [0,1,2,3,4] Explanation: Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively. It doesn't matter what values are set beyond the returned length.

 

Constraints:

• 0 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• nums is sorted in ascending order.

 

문제 풀이:

추가 공간을 쓰면 안된다고 해서 중복된 수열이 나올때마다 맨 뒤로 보냈다. 그랬더니 많은 시간이 소요되었다.

 

class Solution {
    public int removeDuplicates(int[] nums) {
        
        int len = nums.length;
        
        int dup = 0;
        if(len == 0){
            return dup;
        }
        
        int tmp = nums[0], i=1, cnt = 1;
        while(i<len && cnt < len){
            if(tmp == nums[i]){
                dup++;
                cnt++;
                int j = i;
                while(j+1<len){
                    nums[j] = nums[j+1];
                    j++;
                }
                nums[len-1] = tmp;
            }
            else {
                cnt++;
                tmp = nums[i];
                i++;
            }
        }
        
        return len - dup;
    }
}

 

답을 봤더니 코드가 짧고 간결해서 자괴감이 들었다. 로직은 토포인터 사용.

i=0으로 j=1로 초기화한다.

i는 prev, j는 cur를 뜻하며 i와 j가 다를 때만 i가 업데이트되고 j는 매번 한칸씩 움직인다. nums[cur]와 nums[prev]가 다르다면 prev+1 자리에 nums[cur]를 복붙한다. 

만약 중복요소가 전혀 없다면 i와 j는 한 칸의 간격이 유지되므로 변화가 없을 것이다.

 

만약 0 0 0 0 1 2 3 이렇게 되어 있다면 

i= 0, j = 4가 되어야 i가 +1되고 1index에 1이 복사될 것이다.

 

그리고 최종 길이는 i+1이 된다.

class Solution {
    public int removeDuplicates(int[] nums) {
        
        int len = nums.length;
        
        if(len == 0){
            return 0;
        }
        
        int i=0;
        for(int j=1; j<len; j++){
            if(nums[i] != nums[j]){
                i++;
                nums[i] = nums[j];
            }
        }
        return i+1;
    }
}