[Codility - Arrays] OddOccurrencesInArray

https://app.codility.com/programmers/lessons/2-arrays/odd_occurrences_in_array/

OddOccurrencesInArray coding task - Learn to Code - Codility

 

- Array의 element수가 최대 100만이므로, n^2 이상의 시간복잡도 알고리즘은 바로 시간초과가 난다.

O(NlogN) 이하의 알고리즘으로 해결해야 한다.

 

- Hash를 활용하기 위해 Map 객체를 활용했다. 전체 데이터를 한 번씩 순회하면서 O(N), 각 순회당 key의 존재 여부를 탐색하는(Map.has()) 데에 O(logN)이 드므로 O(NlogN)으로 해결할 수 있다. (map 객체는 key를 red-black Tree로 저장하므로 탐색에 O(logN)을 보장한다고 한다.

 

function solution(A) {
    let sH = new Map()
    // key가 존재하면 value += 1, 아니면 value를 1로 세팅
    for(let num of A){
        if(sH.has(num)) sH.set(num, sH.get(num)+1)
        else sH.set(num, 1)
    }
    // value가 홀수이면 unpair하므로 답이다.
    for(let [key, value] of sH){
        if(value % 2 !== 0) return key
    }
}