[Codility] Lesson2- OddOccurrencesInArray

이 문제는 두 방법으로 풀었다.

첫 번째 방법은 Linked List , 속도 개선좀 해보려고 사용한건데 역부족이었다.

"66점" 달성, 그래도 배열은 44점인가 그랬는데 그것보단 나은것 같다.

시간복잡도는 ,, O(n^2) ,, 

import java.util.*;
class Solution {
    public int solution(int[] A) {
        Queue<Integer> list =new LinkedList<Integer>();
        for(int i=0; i<A.length; i++){
            if(list.contains(A[i]))
                list.remove(A[i]);
            else
                list.add(A[i]);
        }
        
        return (int)list.peek();
    }
}

사실 Set까진 생각을 못하고 Map으로 지지고 볶다가 도저히 Key 처리가 안되길래 결국 구글찬스

아맞다 Set ㅋㅋㅋㅋㅋㅋㅋㅋㅋ 나 바벙 왜 맵은생각하면서 셋은생각못하니 ,,? ㅠ__ㅠ

그래서 만점짜리 코드는 ,

import java.util.*;
class Solution {
    public int solution(int[] A) {
        Set<Integer> set=new HashSet<Integer>();
        for(int i=0; i<A.length; i++){
            if(set.contains(A[i]))
                set.remove(A[i]);
            else
                set.add(A[i]);
        }
        
        return set.iterator().next();
    }
}

Set 정리 한번 해야겠당 !

그 김에 해시트리 해시셋도 ~