lintcode.82 落单的数

2018-06-17 21:58:26来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

落单的数

 

给出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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:hdu 6107--Typesetting(倍增)

下一篇:拨开字符编码的迷雾--编译器如何处理文件编码