26. Remove Duplicates from Sorted Array - C++ 풀이

www.leetcode.com/problems/remove-duplicates-from-sorted-array/

Remove Duplicates from Sorted Array - LeetCode

Given 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]);
}

 중복된 원소가 있는 배열에서 서로 다른 원소의 개수를 구하면 된다. 단 임시 배열을 사용하지 말고 입력된 배열을 수정해서 extra memory를 사용하지 않아야 한다. 리턴값을 체크함과 동시에 공간복잡도를 보는 문제이다. 

#include <iostream>
#include <vector>
using namespace std;

class Solution {
   public:
    int removeDuplicates(vector<int>& nums) {
        int idx = 1;
        int size = nums.size();
        if(size <= 1) { 
            return size; 
        }
        for (int i = 0; i < size - 1; ++i) {
            if (nums[i] != nums[i + 1]) {
                nums[idx++] = nums[i + 1];
            }
        }
        return idx;
    }
};

 

- 0. vector의 길이가 1 미만이면 바로 길이를 리턴해준다.

- 1. 배열이 이미 정렬되어 있다. 그러므로 인덱스 0부터 순차적으로 원소갯수를 세어나간다. 

두 개의 포인터 idx, i를 이용할 수 있다.

인접한 인덱스의 값끼리 비교해나가면서 값이 다른 경우, nums 배열에 빈 배열이 있는 마냥

새로운 값으로 덮어 씌워나간다.

- 2. 순회가 끝나면 [1,2,2,3,3,3,4,4,4] 배열은 [1,2,3,4,3,3,4,4,4] 가 되고 idx는 1에서부터 3번 증가해서 4로 끝난다.

4를 리턴해준다

keyword: in-place 알고리즘

www.geeksforgeeks.org/in-place-algorithm/

In-Place Algorithm - GeeksforGeeks

여기서 in-place라는 뜻은 그 자리에서 바로 행한다는 의미.

추가적인 메모리공간을 사용하지 않고(혹은 적게 사용) 기존에 있는 공간(input 변수)에서 manipulating 한다는 뜻이다. 

일반적인 방식에서는 입력이 출력에 의해 덮어 쓰여진다.

bubble sort, selection sort, insertion sort, heapsort는 이러한 방식으로 구현할 수 있다.