[LeetCode] Algorithm/Single Number/LeetCode 136

배열 내에서 엘리먼트가 두번씩 반복되고 한개의 엘리먼트만 한 번 존재할 때,
한개의 값만 가지는 엘리먼트를 찾는 문제.

linear runtime과 추가적인 메모리 사용 없이 해결해야 한다.
Linear Time complexity는 O(n) complexity로 불리며, 인풋의 사이즈만큼 실행시간이 증가하는 시간 복잡도를 의미한다.
for loop, while loop, forEach 등이 해당되고 인풋의 개수가 늘어날 수록 처리 시간도 우상향 증가한다.

linear runtime 이용

let singleNumber = function(nums) {

    let result = 0;
    for(let i = 0; i < nums.length; i++){
        result ^= nums[i]
    }
    
    return result

• for loop는 모든 인덱스를 다 순회하기 때문에 nums 배열의 크기만큼 실행시간이 늘어나는 시간복잡도를 가진다.
• 데이터의 크기가 5배가 되면, 처리시간도 5배가 된다.

XOR 연산자 이용

양쪽의 비트가 서로 다르면 1, 같으면 0을 반환하는 연산자로 해당 문제에서는 십진법을 이진법화 하여 비트를 비교한 뒤 계산하면 된다.

입력 데이터가 [2,2,1] 이라고 가정

    let result = 0;
    for(let i = 0; i < nums.length; i++){
        result ^= nums[i]
        // 1) 0번째 인덱스 2 : 0 ^= 10(===2) 
        // 		=> 1의 자리 0과 0을 비교 = 0, 십의 자리 0만 존재 = 1 / 반환값 : 이진법 10
        // 2) 1번째 인덱스 2 : 10 ^= 10
        // 		=> 1의 자리 0과 0을 비교 = 0, 십의 자리 1 과 1비교 = 0 / 반환값 : 이진법 00
        // 3) 2번째 인덱스 1 : 00 ^= 01
        // 		=> 1의 자리 0과 1을 비교 = 1, 십의 자리 X / 반환값 : 이진법 1
        
        // 최종 리턴값 : 1 
        
    }
    
    return result

• 배열의 모든 요소를 순회했을 때, 두 개씩 존재하는 요소는 사라지고 짝이 없는 요소가 남는다.

^(XOR) 두 비트가 서로 다르면 1, 같으면 0