Single Number

「找单数」系列题,技巧性较强,需要灵活运用位运算的特性。

Question

Given 2*n + 1 numbers, every numbers occurs twice except one, find it.

Example
Given [1,2,2,1,3,4,3], return 4

Challenge
One-pass, constant extra space

题解

根据题意,共有2*n + 1个数,且有且仅有一个数落单,要找出相应的「单数」。鉴于有空间复杂度的要求,不可能使用另外一个数组来保存每个数出现的次数,考虑到异或运算的特性,根据x ^ x = 0x ^ 0 = x可将给定数组的所有数依次异或,最后保留的即为结果。

class Solution:
    # @param A, a list of integer
    # @return an integer
    def singleNumber(self, A):
        ans = A[0]
        for i in range(1, len(A)):
            ans = ans ^ A[i]
        return ans
class Solution:
    # @param {integer[]} nums
    # @return {integer}
    def singleNumber(self, nums):
        return reduce(operator.xor, nums)
class Solution:
    # @param {integer[]} nums
    # @return {integer}
    def singleNumber(self, nums):
        return reduce(operator.xor, nums)

results matching ""

    No results matching ""