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

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

既然是空间复杂度的限制
所以

int res = 0;

for( int i = 0; i < n; i++ ){

res ^= arr[i];

}

return res;

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

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

只有注册用户登录后才能发表评论。


相关文章: 判断一个数是4的整数次幂不能使用库函数不能定义其他的变量 strcpy逆序拷贝有一个长度为998的数组，里面是1-1000并且无重复的数。只用一次遍历，不能使用集合，算出1-1000不在这个数组中的那2个数概率问题，有个人每天都去看流星，他一个月能看到流星的概率是91%，那他半个月能看到流星的概率是多少？（每天能看到流星的事件是独立的）有2.5亿个整数存放在一个文件中，（已知内存容量没有此文件大）如何判断出这个文件中有多少个不相同的数。骆驼吃香蕉问题 1000瓶药水，其中至多有1瓶剧毒，现在给你10只小狗在24小时内通过小狗试药的方式找出哪瓶药有毒或者全部无毒（小狗服完药20小时后才能判断是否中毒）判断另一字符串的所有字母是否在母串中都有数列L中有n个整数，其中K个数字出现了两次，1个数字出现了一次，所以n=2k+1；请在使用O（1）空间的前提下，尽快找出只出现一次的那个数字，并说明算法的复杂度。

网站导航: 博客园 IT新闻 BlogJava 知识库博问管理