single-number.cpp (1032B)
1 #include <iostream> 2 #include <vector> 3 #include <unordered_map> 4 using namespace std; 5 6 7 // Time: Memory: 8 // 27ms 20.2MB 9 // 35.71% 14.99% 10 // 11 // I think this is a fine solution to the problem using maps albeit not the fastests. 12 13 14 int singleNumber(vector<int>& nums) { 15 unordered_map<int , int> searching_vals; 16 17 //Iterate through the vector and place the vals in a map 18 for(int i = 0 ; i < nums.size() ; ++i){ 19 if(searching_vals.find(nums[i]) == searching_vals.end()){ 20 searching_vals.insert(pair(nums[i] , 1)); 21 } 22 else{ 23 auto it = searching_vals.find(nums[i]); 24 it->second = 2; 25 } 26 } 27 28 //Iterate through the list to find the orphan value. 29 for(auto itr = searching_vals.begin(); itr != searching_vals.end() ; ++itr){ 30 if(itr->second == 1){ 31 return itr->first; 32 } 33 } 34 return 0; 35 36 } 37 38 39 40 int main(){ 41 //Ans should be 4 42 vector <int> vec = {0 , 10, 0, 10, 2, 2, 3, 4, 3}; 43 cout << singleNumber(vec) << endl; 44 45 }