LeetCode 136 Single Number(只出现一次的数字)

  1. 云栖社区>
  2. 博客>
  3. 正文

LeetCode 136 Single Number(只出现一次的数字)

nomasp 2016-02-18 15:24:00 浏览436
展开阅读全文
版权声明:转载请联系本人,感谢配合!本站地址: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;
}
};

网友评论

登录后评论
0/500
评论
nomasp
+ 关注