파이썬의 단일 숫자 II

비어 있지 않은 정수 배열이 있다고 가정하고 모든 요소는 정확히 한 번 나타나는 하나를 제외하고 세 번 나타납니다. 우리는 단일 요소를 찾아야 합니다. 따라서 배열이 [2,2,3,2]이면 출력은 3이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 배열에서 요소의 절대값을 가져와 최대값을 찾아 max_num에 저장합니다.

• max_bits :=정수(log max_num base 2) + 2

• list1 :=크기가 max_bits이고 요소가 0인 빈 목록

• 숫자의 각 숫자에 대해 -

  • 위치 :=0

  • num이 0이 아니고 pos 인 동안

    • no가 홀수이면 list1[pos]을 1만큼 증가시킵니다.

    • n :=n / 2 및 pos 1 증가

• 0 ~ max_bits 범위의 i에 대해

  • list1[i] :=list1[i] 모드 3

• 위치 :=0, 해상도 :=0

• max_bits

  범위의 i에 대해

  • list1[i]가 0이 아니면 result :=result + 2^pos

  • 위치 :=위치 + 1

• list1[max_bits - 1]이 1이면 res :=-(2^max_bits - res)

• 반환 해상도

예제(파이썬)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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