版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50686403
翻译
给定一个整型数组,除了某个元素外其余元素均出现两次。找出这个只出现一次的元素。
备注:
你的算法应该是一个线性时间复杂度。你可以不用额外空间来实现它吗?
原文
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?
分析
请参照上一题:LeetCode 260 Single Number III(只出现一次的数字3)(*)
还有一道与之对应的题:LeetCode 137 Single Number II(只出现一次的数字 II)(*)
代码
class Solution {
public:
unsigned int FindFirstBigIs1(int num) {
int indexBit = 0;
while (((num & 1) == 0) && (indexBit < 8 * sizeof(int))) {
num = num >> 1;
++indexBit;
}
return indexBit;
}
int singleNumber(vector<int>& nums) {
if (nums.size() <= 0) return NULL;
int resultExclusiveOR = 0;
for (int i = 0; i < nums.size(); ++i)
resultExclusiveOR ^= nums[i];
unsigned int indexOf1 = FindFirstBigIs1(resultExclusiveOR);
int singleNum = 0;
for (int j = 0; j < nums.size(); ++j) {
singleNum ^= nums[j];
}
return singleNum;
}
};