【codility】Lesson 2:Arrays OddOccurrencesInArray

#subject
Lesson 2:Arrays OddOccurrencesInArray
N個（奇数）の要素を持つ配列の中に、ペアのいない要素があり、その要素を返す問題。
例）
A = {9, 3, 9, 3, 9, 7, 9}の場合は7を返す。
#submit
score100にたどり着くまでに、計算速度の課題にぶち当たった。メモリをクリアできないとscore77止まり。

#program
結局メモリの課題はクリアできず、過去に解いた方のものを理解した。参考
このXORに自分ではたどり着けなかった。こんなに短くてシンプルなプログラムがかけると気持ち良いだろうな。とても学びになった。

oddOccurrencesInArray.cpp

#include<iostream>
#include<vector>
using namespace std;

int solution(vector<int> &inputArray, int N) {

    int oddOccurrences = 0;
    for (int i : inputArray) {
        oddOccurrences ^= i;
    }
    return oddOccurrences;
}

演算速度には引っかかってしまったが、自分で考えたプログラムはこんな感じである。

oddOccurrencesInArray_NG.cpp

#include<iostream>
#include<vector>
#include<map>
using namespace std;

int solution(vector<int> &inputArray, int N) {

	map<int, int> number;

	//count occurrences
	for (int i : inputArray) {
		auto itr = number.find(i);  // find key i
		if (itr != number.end())    //if there are the key i
            number.erase(i);
		else
		    number.insert(make_pair(i, 1));
	}

	//find the unpare element
	for (auto x : number) {
			return x.first;
	}
	return 0;