[ LeetCode | Java ] 26. Remove Duplicates from Sorted Array

dokim·2023년 8월 24일

[LeetCode] Top 150 leetcode

[LeetCode] Top Interview 150

목록 보기

6/51

🏷️26. Remove Duplicates from Sorted Array

1. 문제 설명

주어진 정수 배열 nums가 비내림차순으로 정렬되어 있을 때, 중복된 요소를 제거하여 각 고유한 요소가 한 번씩만 나타나도록 합니다. 요소의 상대적인 순서는 유지되어야 합니다. 그런 다음 nums의 고유한 요소의 수를 반환합니다.
nums의 고유한 요소의 수를 k라고 가정하고, 허용되기 위해 다음을 수행해야 합니다:
- nums 배열을 변경하여 nums의 처음 k개 요소에는 nums가 처음에 있던 순서대로 고유한 요소가 포함되어야 합니다. nums의 나머지 요소와 nums의 크기는 중요하지 않습니다.
- k를 반환합니다.

예시 1:

입력: nums = [1,1,2]
 출력: 2, nums = [1,2,_]
 설명: 함수는 k = 2를 반환해야 하며 nums의 처음 두 요소는 각각 1과 2입니다. 
반환된 k 외에 무엇을 남겨두는지는 중요하지 않습니다(따라서 밑줄로 표시됩니다).

예시 2:

입력: 숫자 = [0,0,1,1,1,2,2,3,3,4]
 출력: 5, 숫자 = [0,1,2,3,4,_,_,_,_, _]
 설명: 함수는 k = 5를 반환해야 하며, nums의 처음 5개 요소는 각각 0, 1, 2, 3, 4입니다. 
반환된 k 외에 무엇을 남겨두는지는 중요하지 않습니다(따라서 밑줄로 표시됩니다).

2. 접근 방식

오름차순으로 정렬이 되어있어 첫번째 정수 기준으로 반복문을 순차적으로 탬색하면서 중복 정수는 넘어가고 다른 정수가 나올 때까지 탐색하며 다른 정수가 나오면 첫번째 정수 다음 두번째 index에 저장합니다.

nums의 길이가 0이면 0 반환
첫번째 정수는 nums[0]에 있으므로 따로 초기화를 할 필요가 없습니다.
그래서 k를 1로 초기화하고 첫번째 정수를 기준으로 다른 정수가 나올 때까지 반복문으로 찾습니다.
다른 정수를 찾으면 다른 정수를 nums의 k번째 index에 저장하고 k를 증가시킵니다.(nums[0]에는 첫번째 정수가 세팅되어 있습니다.)

3. 의사 코드

	if(nums.length == 0)
    	0반환
    
    k = 1
    for(nums의 두번째 index에서부터 탐색)
    	if(첫번째 정수 != n번째 정수)
        	num[k++] = nums[n번째 정수]

4. 구현 코드

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

시간 복잡도: O(n)
공간 복잡도: O(1)

5. 개선 사항

import java.util.*;  
import java.util.stream.*;  
  
class Solution {  
    public int removeDuplicates(int[] nums) {  
        List<Integer> list = Arrays.stream(nums).distinct()  
            .boxed().collect(Collectors.toList());  
        for(int i = 0; i < list.size(); i++) {  
            nums[i] = list.get(i);  
        }  
        return list.size();  
    }  
}