Python中的单数II

假设我们有一个非空的整数数组，每个元素出现3次，除了一次，它恰好出现一次。我们必须找到一个元素。因此，如果数组为[2,2,3,2]，则输出为3。

为了解决这个问题，我们将遵循以下步骤-

• 通过从数组中获取元素的绝对值来找到最大值，并将其存储到max_num中

• max_bits：=（log max_num以2为底的整数）+ 2

• list1：=一个大小为max_bits且元素为0的空列表

• 对于以num为单位的每个num-

• 如果否为奇数，则将list1 [pos]加1

• n：= n / 2并增加pos 1

• 位置：= 0

• 而num不为0并且pos <max_bit

• 对于我在0到max_bits范围内

• list1 [i]：= list1 [i] mod 3

• pos：= 0，res：= 0

• 对于我在max_bits范围内

• 如果list1 [i]不为0，则结果：=结果+ 2 ^ pos

• pos：= pos + 1

• 如果list1 [max_bits-1]为1，则res：=-（2 ^ max_bits-res）

• 返回资源

范例(Python)

让我们看下面的实现以更好地理解-

import math
class Solution(object):
   def singleNumber(self, nums):
      max_num = max(map(abs, nums))
      max_bits = (int)(math.log(max_num,2)) + 2
      list1 = [0 for i in range(max_bits)]
      for no in nums:
         pos = 0
         while (no != 0 and pos < max_bits):
            if (no & 1 != 0):
               list1[pos] += 1
            no >>= 1
            pos += 1
      for i in range(max_bits):
         list1[i] %= 3
      pos = 0
      result = 0
      for i in range(max_bits):
         if (list1[i] != 0):
            result += (2 ** pos)
         pos += 1
      print (list1, max_bits)
      if (list1[max_bits - 1] == 1):
         result = -(2 ** max_bits - result)
      return (result)
ob = Solution()print(ob.singleNumber([2,2,3,2]))

输入值

[2,2,3,2]

输出结果

[1, 1, 0] 3
3