LeetCode #136 #137 #260 2018-07-

136. Single Number

https://leetcode.com/problems/single-number/description/

这道题，本身要求是找出唯一一个在数组中出现一次的整数，而其他都会出现两次。这里利用到了位运算中异或的性质，就是两个相同的数进行异或会得到0，并且任何一个数与0的异或还是原数。利用上面的性质，只要把数组中的元素一一异或起来，因为出现两次的会互相抵消，最后会只剩下那个出现一次的整数。这个方法只需要一次扫描，即O(n)的时间复杂度，而空间上也不需要任何额外变量，即O(1)的空间复杂度。
代码如下：

class Solution:
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        from functools import reduce
        return reduce(lambda x, y: x ^ y, nums)

137. Single Number II

https://leetcode.com/problems/single-number-ii/description/

提供一种nk + 1类型题目的通解。上面的方法就没办法了，因为出现三次就不能利用异或的性质了。 算法是对每个位出现1的次数进行统计，因为其他元素都会出现三次，所以最终这些位上的1的个数会是3的倍数。如果我们把统计结果的每一位进行取余3，剩下的结果就会剩下那个出现一次的元素。这个方法对于出现k次都是通用的，包括上面的Single Number也可以用这种方法，不过没有纯位运算的方法效率高。总体只需要对数组进行一次线性扫描，统计完之后每一位进行取余3并且将位数字赋给结果整数，这是一个常量操作（因为整数的位数是固定32位），所以时间复杂度是O(n)。而空间复杂度需要一个32个元素的数组，也是固定的，因而空间复杂度是O(1)。
代码如下：

class Solution:
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        result = 0
        for i in range(32):
            temp = 0
            for num in nums:
                temp += (num >> i) & 1
            result |= (temp % 3) << i
            if i == 31 and temp % 3 == 1:
                result -= 1 << 32
        return result

260. Single Number III

https://leetcode.com/problems/single-number-iii/description/

这道题是2n + 2的问题。将所有数异或后得到的结果c是a异或b的结果，那么问题来了，我们该如何将a和b区别开至两组。由于c一定不为0的，所以c的某一位一定不为0，所以我们可以根据这一位将所有数分成2组，即可得到结果。
代码如下：

class Solution:
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        c = 0
        for num in nums:
            c ^= num
        digit = 0
        for i in range(32):
            if c >> i & 1 != 0:
                digit = i
                break
        result = [0, 0]
        for num in nums:
            if num >> digit & 1 == 0:
                result[0] ^= num
            else:
                result[1] ^= num
        return result