数列L中有n个整数,其中K个数字出现了两次,1个数字出现了一次,所以n=2k+1;请在使用O(1)空间的前提下,尽快找出只出现一次的那个数字,并说明算法的复杂度。

数列L中有n个整数,其中K个数字出现了两次,1个数字出现了一次,所以n=2k+1;请在使用O(1)空间的前提下,尽快找出只出现一次的那个数字,并说明算法的复杂度。

既然是空间复杂度的限制
所以 
int res = 0;
forint i = 0; i < n; i++ ){
    res 
^= arr[i];
}

return res;
最终有
1.两个相同的数异或结果为0
2.0与任何数异或结果还是这个数

posted on 2011-09-19 19:28 メmarsメ 阅读(1135) 评论(0)  编辑 收藏 引用 所属分类: AL


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


<2011年12月>
27282930123
45678910
11121314151617
18192021222324
25262728293031
1234567

导航

统计

常用链接

留言簿

随笔分类

随笔档案

文章分类

文章档案

搜索

最新评论

阅读排行榜

评论排行榜