C++] codility - OddoccurrencesInArray

1.설명

 

 -방법

1)XOR

2)배열에 추가/삭제

2.코드

 1)벡터에 추가/삭제

->O(N**2)

>>vector.find() 자체의 속도복잡도가 느린듯하다. 

>>set을 이용하면 됨.

#include <algorithm> int solution(vector<int> &A) { // write your code in C++11 (g++ 4.8.2) vector<int> temp; vector<int>::iterator iter; for(int i=0; i<A.size(); i++) { iter = find(temp.begin(), temp.end(), A[i]); if(iter == temp.end()) temp.push_back(A[i]); else temp.erase(iter); //iter = find( } return *temp.begin(); }

https://codility.com/demo/results/trainingQW5D3W-EZE/

2)xor

int solution(vector<int> &A) { // write your code in C++14 (g++ 6.2.0) int key=0; int index = 0, remainder=0; index=A.size()/2; remainder=A.size()%2; for(int i=0; i<index; i++) { key^=A[i]; key^=A[A.size()-1-i]; } if(remainder!=0) key^=A[index]; return key; }

https://codility.com/demo/results/trainingNFHZ4D-XDM/