Given an array of integers, every element appears twice except for one. Find that single one.
最近两个月事情很多,论文开题,家庭变故,都没有时间学习、做题,也没有时间写博客。现在回来再看感觉自己之前很多东西都做的不到位,所以把之前做过的题目也都翻出来做一下,温故知新嘛~
现在回忆一下,这是我做的第一道leetcode题目,也是我最初接触算法的时候做的。当时拿到题目简直是丈二和尚,感觉被leetcode的高深莫测深深折服了。后来想了很久感觉用本科二年级学过的数据结构里的哈希表可以解决这个问题,但是苦于c++水平太低,对关联容器这种外星物种更是一无所知,所以就一直没能实现。然后就开始猥琐的上网搜答案,答案一边倒倒向用位运算——异或解决这个问题,又一次感觉自己的智商被碾压。
任何数和它本身异或都得零,看到这句话瞬间感觉好猥琐(可以脑补屌丝码农自我安慰的场景,事后四大皆空,更不可能有孩子)。任何数和零异或都得它本身,这......屌丝终归是屌丝TT
言归正传,下边是这个思路的代码
class Solution{ public: int singleNumber(int A[], int n) { int answer = A[0]; for(int i = 1;i < n; i++){ answer = answer ^ A[i]; } return answer; } };
class Solution{ public: int singleNumber(int A[], int n) { mapm; for (int i = 0; i < n; i++){ if (m.count(A[i])){ m[A[i]]++; } else{ m[A[i]] = 1; } } for (map ::iterator it = m.begin(); it != m.end(); it++){ if (it->second == 1) return it->first; } return 0; } };