Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

[LeetCode]Single Number-2014.01.16

Posted on 2014-01-16 03:19 Uriel 阅读(93) 评论(0)  编辑 收藏 引用 所属分类: LeetCode
给一堆数,其中只有一个只出现过1次,其他都出现2次,找出那个出现1次的,其实是简单位运算,但是就没往位运算上想,还在纠结怎么可能空间复杂度O(1),看了解题报告恍然大悟:http://www.cnblogs.com/feiling/p/3349654.html

就是不断做异或运算就好,最后剩下的就是只出现了1次的那个数

 1 class Solution {
 2 public:
 3     int singleNumber(int A[], int n) {
 4         int tp = 0;
 5         if(!n) return 0;
 6         for(int i = 0; i < n; ++i) {
 7             tp = tp ^ A[i];
 8         }
 9         return tp;
10     }
11 };

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理