一道c++编程题求解!

C++语言 码拜 10年前 (2015-05-11) 828次浏览 0个评论

Given an array of integers, every element appears twice except for one. Find that single one.

class Solution {
public:
    int singleNumber(vector<int>& nums) 
    {
        if(nums.empty()) return 0;
        int first = nums[0];
        for(int i = 1; i<nums.size();i++) {
            first = first ^ nums[i];
        }
        return first;
    }
};

这个没有看懂,有没有大神帮忙解答下!谢谢!

20分
理解异或运算的特点
无论a是多少,a^a都是0;
汇编中常出现
xor eax,eax   ;eax清零
如果该数组是这样的{a,a,b,b,c}
则a^a^b^b^c=0^c=c
10分
0^a(a为任何数)=a
a^a=0

异或还符合交换律

所以只要是相同的想异或总为0,到最后就是0跟那个没有任何相同数异或,答案就是那个数字了

请问同样的问题,当每个数出现三次,一个数出现一次的情况怎么求解?有没有通用的技巧?有没有什么关于位运算发的详解,总结什么的?
10分
由于只有一个是出现一次的,其他都是出现2次,而相同的数字异或的结果为0,即:a^a=0
因此最后就留下一个没有成对出现的那个数字了

CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明一道c++编程题求解!
喜欢 (0)
[1034331897@qq.com]
分享 (0)

文章评论已关闭!