20220508 Odd Occurrences In Array

title: "Codility OddOccurrencesInArray"

date: "2022-05-08"

풀이1. 맵으로 중복 체크.

not perfect. 시간 리미트 걸림. Total score : 77% 매번 삭제하지 않고, 값을 증가시키는 방법법으로 하였으나 마찬가지

// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
#include <asm-generic/errno.h>
#include <map>

int solution(vector<int> &A) {
    int result = 0;
    map<int, int> map;// = map<int, int>();

    // write your code in C++14 (g++ 6.2.0)
    //1. special case 정리
    if(A.size() == 1) return A[0];
    //2. vector를 돌며 map을 보고 값이 없으면 1추가, 있으면 삭제
    vector<int>::iterator iter;

    for (iter = A.begin(); iter != A.end(); iter++) {
        //있으면 지우고, 없으면 추가
        auto dupcheck = map.find(*iter);
        if(dupcheck != map.end()) { dupcheck->second += 1;
        }
        else                map.insert({*iter, 1});
    }
    //3. map에 남은 값의 키를 리턴
    
    for(auto mapiter = map.begin(); mapiter != map.end(); ++mapiter){
        if((mapiter->second % 2) ==  1)
            return mapiter->first;
    }
    
    return result;
}

풀이2. 정렬 후 홀수 체크

정렬에서 O(nlogn) 후 각 아이템을 O(n) 하므로 O(nlogn) + O(n) = O(nlogn)하여 통과

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
#include <algorithm>

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    
    sort(A.begin(), A.end());
    auto iter = A.begin();
    int beforeValue = *iter;
    int count = 1;
    for(++iter; iter != A.end(); ++iter){
        if(*iter == beforeValue)    ++count;
        else if( (count % 2) != 0 ) return beforeValue;
        else {
            beforeValue = *iter;
            count = 1;
        }
    }
}