LeetCode: Single Number I && II

I title:

Given an array of integers, every element appearstwiceexcept for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

思路：异或

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

title：

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

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

思路：

这里我们需要重新思考，计算机是怎么存储数字的。考虑全部用二进制表示，如果我们把第 i^th 个位置上所有数字的和对3取余，那么只会有两个结果 0 或 1 (根据题意，3个0或3个1相加余数都为0). 因此取余的结果就是那个 “Single Number”.

一个直接的实现就是用大小为 32的数组来记录所有位上的和。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        vector<int> v(32,0);
        int result = 0;
        for (int i = 0; i < 32; i++){
            for (int j = 0 ;j < nums.size(); j++){
                if ((nums[j] >> i) & 1)
                    v[i]++;
            }
            result |= ((v[i] % 3) << i);
        }
        return result;
    }
};

这个算法是有改进的空间的，可以使用掩码变量：

ones 代表第i^th位只出现一次的掩码变量
twos 代表第i^th位只出现两次次的掩码变量
threes 代表第i^th位只出现三次的掩码变量

假设在数组的开头连续出现3次5，则变化如下：

ones = 101
twos = 0
threes = 0
--------------
ones = 0
twos = 101
threes = 0
--------------
ones = 0
twos = 0
threes = 101
--------------

当第 i^th位出现3次时，我们就ones 和twos 的第i^th位设置为0. 最终的答案就是 ones。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int one = 0, two = 0, three = 0;
        for (int i = 0; i < nums.size(); i++){
            two |= (one & nums[i]);
            one ^= nums[i];
            three = one & two;
            one &= ~three;
            two &= ~three;
        }
        return one;
    }
};

优质内容筛选与推荐>>
1、Milk Pails（BFS）
2、进程和线程有什么区别
3、Apple技术支持
4、Win7下搭建Go语言开发环境
5、leetcode python 1.Two Sum

0 │ 收藏 │ 举报

朋友将在看一看看到

分享想法到看一看