C++
(1)异或操作
3^3=0
(2)for (auto &i : Obejuct) {}
class Solution {
public:
/**
* @param A: Array of integers.
* return: The single number.
*/
int singleNumber(vector<int> &A) {
// write your code here
int ret = ;
for (auto &i : A) {
ret ^= i;
}
return ret;
}
};
本题扩展
1.一个数组中有两个元素只出现一次,其他所有元素都出现两次,求这两个只出现一次的元素
[解题思路]
将数组所有元素都进行异或得到一个不为0的结果,根据这个结果中的不为0的某一位将数组分成两组
将两组中的元素进行异或,如两个数组的异或值都不为0,则得到最后结果
2.一个数组中有一个元素只出现1次,其他所有元素都出现k次,求这个只出现1次的元素
[解题思路]
当k为偶数时,同lss
当k为奇数时,将数组中每个元素的每一位相加mod k,得到结果即位出现1次的元素,时间复杂度O(nlen),空间复杂度为O(1)