[LeetCode] Single Number

문제링크

Single Number - LeetCode

 

주어진 배열에서 single number을 찾는 문제이다. (중복된 요소가 없는 값)

접근 방법

단순하게 배열을 정렬하고 완전 탐색으로 풀이하였다.

nums.sort((a, b) => a - b);
    
for(let i = 0; i < nums.length; i++){
    if(nums[i] !== nums[i-1] && nums[i] !== nums[i+1]) return nums[i];
}​

처음 시작은 undefinded !== nums[0] && nums[0] !== nums[1]
마지막은 nums[nums.length - 2] !== nums[nums.length - 1] && nums[nums.length - 1] !== undefined
이기 때문에 처음 숫자가 유일한 값이던 마지막 숫자가 유일한 값이던 모두 처리할 수 있다.

간단하게 풀이하여 다른 방법도 생각해보았다.
현재 값을 기준으로 배열을 나누고, 나눈 배열을 합쳐서 현재 값이 있는지 판단하는 방식으로 접근하였다.
[1,2,3,4,5] => 현재값이 3일때 [1,2] [4,5]를 나누고 합쳐서 [1,2,4,5]에 3이 있는지 파악

for(let i = 0; i < nums.length; i++){
    prevArr = nums.slice(0, i);
    nextArr = nums.slice(i+1, nums.length);
    if(!prevArr.concat(nextArr).includes(nums[i])) return nums[i];
}​

배열을 새로 concat하는 과정에서 O(n) & for문에서 O(n)의 시간이 소요되므로
O(n^2)이고, 새로운 배열을 만드므로 공간복잡도도 매우 떨어진다.

 

// 효율적 풀이

/**
 * @param {number[]} nums
 * @return {number}
 */

var singleNumber = function(nums) {
    nums.sort((a, b) => a - b);
    
    for(let i = 0; i < nums.length; i++){
        if(nums[i] !== nums[i-1] && nums[i] !== nums[i+1]) return nums[i];
    }
    
};

 

// 비효율적 풀이

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    for(let i = 0; i < nums.length; i++){
        prevArr = nums.slice(0, i);
        nextArr = nums.slice(i+1, nums.length);
        if(!prevArr.concat(nextArr).includes(nums[i])) return nums[i];
    }
};