[리트코드] Remove Element

https://leetcode.com/explore/learn/card/fun-with-arrays/526/deleting-items-from-an-array/3247/

Explore - LeetCode

주어진 val의 값과 배열의 원소가 같으면 해당 원소를 제거하고 val의 값과 다른 원소들의 개수를 리턴하는 문제

힌트를 보면 two pointer 알고리즘을 활용하여 풀어보라고 한다. 풀어보니 two pointer 알고리즘에 대해 아직 잘 모르는 것 같아서 기록.

풀이 방법

// 시간 복잡도 : O(n)
// 공간 복잡도 : O(1)
const removeElement = function(nums, val){
	let i = 0;
	for (let j = 0; j < nums.length; j++) {
        if (nums[j] != val) {
            nums[i] = nums[j];
            i++;
        }
    }
    return i;
}

// 제거할 요소가 드물 경우 
// 시간 복잡도 : O(n)
// 공간 복잡도 : O(1)
const removeElement2 = function(nums, val){
	let i = 0;
	let n = nums.length;
    while (i < n) {
        if (nums[i] == val) {
				// 같은 값임녀 끝에 있는 값을 재할당
            nums[i] = nums[n - 1];
            // reduce array size by one
            n--;
            // n의 값을 줄여서 끝까지 탐색하지 않게 한다.
        } else {
            i++;
            // 다른 값이면 i를 증가시켜 다음 원소를 탐색하게 한다.
        }
    }
    return n;
}