1.第一種解法的復(fù)雜度是O(32*n)
注意操作
# -*- coding:utf-8 -*-
import ctypes
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
array = []
for i in range(32):
array.append(0)
res = 0
for i in range(32):
for num in nums:
array[i] += (num >> i) & 1
# 先判斷該位是不是1, 再根據(jù)i左移, 再或運(yùn)算即可
res |= ((array[i] % 3) << i)
################################################################### 1
'''本來可以導(dǎo)入模塊的話,很簡單
return ctypes.c_int(res).value'''
################################################################### 2
#轉(zhuǎn)化成二進(jìn)制的字符串,截掉前兩個(gè)字符,再變成字符list,再轉(zhuǎn)化成int的list
strings = bin(res)[2:]
if len(strings) < 32: #正數(shù)可能不足32位，所以要補(bǔ)
strings = '0' * (32 - len(strings)) + strings
numlist = map(lambda x: ord(x) - ord('0'), list(strings))
rest = 0
for i in range(31):
rest = rest * 2 + numlist[i+1]
rest += numlist[0] * (-1) * 2147483648
return rest
s = Solution()
s.singleNumber([1000,2,2,2,3,3,3,4,4,4])
# print s.singleNumber()
2.第2種解法的復(fù)雜度是O(n)
構(gòu)造三進(jìn)制糖声，先只考慮ones， twos绊起， threes為 1 bit的情況會(huì)更好
class Solution {
public:
int singleNumber(int A[], int n) {
int ones = 0;
int twos = 0;
int threes = 0;
int i = 0;
for(i = 0; i < n; i++){
twos |= ones & A[i];
ones ^= A[i];
threes = ones & twos;
ones &= ~threes;
twos &= ~threes;
}
return ones;
}
};
