lintcode.82 落单的数
2018-06-17 21:58:26来源:未知 阅读 ()
落单的数
给出2*n + 1 个的数字,除其中一个数字之外其他每个数字均出现两次,找到这个数字。
给出 [1,2,2,1,3,4,3],返回 4
一次遍历,常数级的额外空间复杂度
这道题很不错,用位运算巧妙的解决。一开始我还想过multiset等等。^位运算才是王道,直接可以解决一堆数中,查找某个奇数个数的数字。
所有数字, ^ 自身等于0,这是这道题的核心。
另外再写一下 ^的常用用法,
用作swap, a=a^b;
b=b^a;
a=a^b;
这个式子就相当于 a=a^b^a。 等同于 a=b;
翻转数字,1^n。
class Solution { public: /* * @param A: An integer array * @return: An integer */ int singleNumber(vector<int> &A) { // write your code here int ans=0; int s=A.size(); for(int i=0;i<s;i++) { ans^=A[i]; } return ans; } };
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 3295 落单的数 九章算法面试题 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash