Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
注意：多关键字的multimap不能使用下标操作。
C++代码如下：
#include<iostream> #include<map> using namespace std; class Solution { public: int singleNumber(int A[],int n) { multimap<int,int> mp; int i; for(i=0;i<n;i++) { mp.insert({A[i],i}); } auto map_it=mp.begin(); while(map_it!=mp.end()) { auto tmp=map_it; tmp++; if((tmp)==mp.end()) return (map_it)->first; if(map_it->first!=(tmp)->first) break; map_it++; map_it++; } return map_it->first; } }; int main() { Solution s; int arr[]={2,4,2,4,5}; cout<<s.singleNumber(arr,5)<<endl; }
第二遍刷：
int singleNumber(int A[],int n) { multiset<int> st; int i; for(i=0;i<n;i++) st.insert(A[i]); for(i=0;i<n;i++) if(st.count(A[i])!=2) break; return A[i]; }
