【Single Num II】cpp

题目：

Given an array of integers, every element appears three times except 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 result = ;

            const int W = sizeof(int)*;

            int *count = new int[W]();

            for (size_t i = ; i < nums.size(); ++i)

            {

                for (size_t j = ; j < W; ++j)

                {

                    count[j] += (nums[i] >> j) & ;

                }

            }

            for (size_t i = ; i < W; ++i)

            {

                if ( count[i]%!= )

                {

                    result += (  << i);

                }

            }

            delete []count;

            return result;

    }

};

Tips:

1. 算法原理：由于都是int型的，只需要记录每个bit上1出现的次数；如果1出现的次数不是3的倍数，则将该位置置为1，并赋值到result中。

这道题主要是熟悉下位运算的各种操作，有时巧用位运算，可以大大提升代码效率。

================================================================

学习了另一种解法，代码如下：

class Solution {

public:

    int singleNumber(vector<int>& nums) {

            int one=, two=, three=;

            for (size_t i = ; i < nums.size(); ++i)

            {

                two |= (one & nums[i]);

                one ^= nums[i];

                three = two & one;

                one &= ~three;

                two &= ~three;

            }

            return one;

    }

};

参考链接：https://leetcode.com/discuss/857/constant-space-solution

简单说就是，用二进制模拟三进制运算。

循环体中的五条语句分别做了如下的事情：

1. 算上nums[i]之后，1出现了两次的bit位数有哪些

（包括两种情况：a.原来就是2次的，nums[i]在该bit上是0；原来是1次的，nums[i]在该bit上是1）。

2. 算上nums[i]之后，1出现了一次的bit位数有哪些。

3. 算上nums[i]之后，1出现了三次的bit位数有哪些

4和5. 满3进位，清空。

这里可能会有一个疑问：1出现次数为一和为二的能否算重了？

假设nums[i]在某一个bit上是0：

　　a. 算two的时候，这一位不会影响原来two这一bit的取值。

　　b. 算one的时候，相当于该bit与0异或，保持不变。

假设nums[i]在某一个bit上是1：

　　a. 算two的时候，如果one在该bit上也是1，则two这一bit取1，如果one在这一位上是0，则two这一bit上不变。

　　b. 算one的时候，相当于该bit与1异或，取反。如果one原来是1，则进位，one置为0；如果one原来是0，则变为1。

对比颜色相同的两端文字，可以知道是不会算重复的。

想到这里还有一个疑问：two = two | (one & nums[i])，如果某一bit上two原来就是1，并且还有进位了，那这？

这种case是不可能出现的：因为one two three初始都是0，假如连着三个nums[i]在某个bit上都为1，则three在该bit上就为1了。后面两条语句，就保证了two和one被清空了，因此永远不会出现two原来是1并且有进位的情况。

======================================================

第二次过这道题，想了一段时间。大体思路已经想出来了，但是位运算操作（“左移多少位再跟1进行与操作”这些的技巧）参考了书上的code。代码还是一次AC了。

class Solution {

public:

    int singleNumber(vector<int>& nums) {

            int int_bits = sizeof(int)*;

            vector<int> count(int_bits,);

            // count each '1' in each bit

            for ( int i=; i<nums.size(); ++i )

            {

                for ( int j=; j<count.size(); ++j )

                {

                    count[j] += (nums[i] >> j) & ;

                    count[j] = count[j] % ;

                }

            }

            // extract single number

            int single = ;

            for ( int i=; i<count.size(); ++i )

            {

                single = single + ( count[i] << i );

            }

            return single;

    }

};

还是这种思路好记一些，二进制代替三进制运算的那个并没有印象了。

巴特西

【Single Num II】cpp

最新文章

热门文章