[Lesson 2] OddOccurrencesInArray

 

첫번째 제출 score : 55

// 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;

int solution(vector<int> &A) {
    // Implement your solution here
    vector<int> unique_list;

    //make unique list ( 중복이 없는 리스트 만들기 )
    for(int i = 0; i < A.size(); i ++)
    {
        unique_list.push_back(A[i]);
    }

    sort(unique_list.begin(), unique_list.end());
    unique_list.erase(unique(unique_list.begin(), unique_list.end()), unique_list.end());

    // 리스트 A의 원소 개수가 1 이하인 수를 반환한다.
    //check element count 
    for(int i = 0; i < unique_list.size(); i ++)
    {
        if(count(A.begin(), A.end(), unique_list[i]) <= 1)
        {
            return  unique_list[i];
        }
    }
}

충격적인 시간 복잡도...

 

두번째 시도 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;

int solution(vector<int> &A) {
    // Implement your solution here
    int list[1000003];

    for(int i = 0; i < A.size(); i++)
    {
        list[A[i]] ++;
    }

    for(int i = 0; i < 1000000; i++)
    {
        if(list[i] != 0 && list[i]%2 != 0) return i;
    }
}