[LeetCode] 4. 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.

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.

배열안에서 중복된 정수를 제거하고 배열의 길이와 그 배열을 출력

python의 경우 remove 함수를 통해 쉽게 배열 안의 element를 삭제할 수 있지만

java는 그런 기능이 없는 것 같다.

그렇다면 메모리의 특징을 고려한 방법을 생각해내야 하는데

중복된 값을 찾아서 그 값을 비워내려면 그 자리를 비워내고 빈 인덱스로 두는게 아닌 뒤 값들을 앞쪽으로 땡겨주어야한다

그러나 하나하나 그런 과정이 복잡하기 때문에

1) 새로운 배열을 만들고

2) 새로운 배열에 기존 배열의 값을 하나씩 뽑아 넣으면서 같은 값이 있는지 체크하면서 넘긴다

라고 생각했지만 문제 조건에서 다른 배열을 만들지 말라고한다 ^^

그렇기 때문에 다른 방법을 생각해 냈다.

1) i번 index의 값이 i+1의 값과 같으면 i+2번째 값을 i+1에 집어넣는다

2) 이상태에서 i가 1씩 증가하면 된다.

class Solution {
    public int removeDuplicates(int[] nums) {
    int i = 0;
    int j = 1;

    while(j < nums.length){
        if(nums[j] == nums[i]){ //j는 사실상 i+1이므로 i+1값과 i값 비교
            j++; // 같으면 i+2로 만들어준다
        } else { // i+2의 값과 i값이 다른 경우이니
            nums[i+1] = nums[j]; //i+2의 값을 i+1에 집어넣어주고
            i++; //1씩증가
            j++; //1씩 증가하면 전부다 한칸씩 뒤로 밀려나기때문에 같은 행위 반복

        }
    }
    return i+1;

    }
}

다른 사람 코드를 훔쳐보면서 꾸역꾸역 만들어내긴 했는데... 분명 더 쉬운 방법이 있으리라 생각하고 좀 찾아봤다.

Set 컬렉션 사용

Set은 중복 값을 허용하지 않는 특성을 가지고 있으므로 하나씩 집어넣다보면 알아서 중복값 제거됨

package workshop8;

import java.util.HashSet;
import java.util.Set;

public class dummy{
    public static void main(String[] args) {

    int [] array = {1,1,2,2,3,3,4,4,5,5,6,6,7,1,2,3,4,5,6};
    System.out.println("array 크기 :" + array.length);
    System.out.println("====================");

    Set<Integer> set = new HashSet<>();

    for(int a : array){
        set.add(a);
    }

    System.out.println(set.size()); // set 크기 확인
    System.out.println("====================");

    for(int a : set) {
        System.out.print(a + " "); // set값 하나씩 출력
    }

    }

}

result:

array 크기 :19
====================
7
====================
1 2 3 4 5 6 7 

결론 : 중복값 제거는 set이 짱이야