leetcode || 136、Single Number
来源：程序员人生 发布时间：2015-06-05 09:29:28 阅读次数：2833次
problem：
Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Hide Tags
Hash Table Bit
Manipulation
题意：1组数，只有1个数出现1次，其他数都出现两次，找出这个数
thinking：
（1）考察位运算，C/C++的异或运算符为 ^
0^a=a;
a^a=0;
a^b=b^a;
(2)这道题的解法就出来了：n个数的异或结果就是待求数
code：
class Solution {
public:
int singleNumber(vector<int>& nums) {
int n=nums.size();
int ret=nums[0];
for(int i=1;i<n;i++)
ret^=nums[i];
return ret;
}
};
本题扩大，参考http://www.cnblogs.com/changchengxiao/p/3413294.html
1.1个数组中有两个元素只出现1次，其他所有元素都出现两次，求这两个只出现1次的元素
[解题思路]
将数组所有元素都进行异或得到1个不为0的结果，根据这个结果中的不为0的某1位将数组分成两组
将两组中的元素进行异或，如两个数组的异或值都不为0，则得到最后结果
2.1个数组中有1个元素只出现1次，其他所有元素都出现k次，求这个只出现1次的元素
[解题思路]
当k为偶数时，同lss
当k为奇数时，将数组中每一个元素的每位相加mod k，得到结果即位出现1次的元素，时间复杂度O(nlen)，空间复杂度为O(1)
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
