题目
给定包含N个正整数的非递减数组A,假设该数组以以下形式保存了某个正整数K的值,即:
例如给定,则。
则给出一个算法,计算出的二进制表示中为1
的比特个数。
例如,程序返回值为4
。
要求:时间复杂度控制在;空间复杂度控制在。
题解
对于二进制的题,一般都要从二进制本质出发,从数组A的定义可以得到:
然后我们对数组中的每一位都加上1,然后合并回到数组A中,得到新的数组B,那么问题就转化为计算数组B代表的K的二进制中比特1
的个数,为了表述方便,我们下文依然用数组A来举例表述。
让我们再次回到二进制的基本概念上来,对于一个二进制数:
那么数组A所代表的数字就变成了:
也就是说,数组A中的每一位数字A[i]
,都代表了K的二进制中低A[i]
位的比特位为1
。
于是问题就简化为,将数组B表示的每个比特位加起来,最后的结果中1
的个数,就是我们想要的结果。
代码实现如下:
def solution(A):
bits = {} # 使用哈希表来存储每一个比特位,可以节省空间
# 如果键值k存在于bits中,那么代表低k位为1
for i in A:
for j in range(i, i + 2):
t = j
while t in bits:
del bits[t] // 逐比特执行加法
t += 1
bits[t] = 1
# 最后输出bits中的键值个数即可
return len(bits.keys())
题外话
然而,这道题是我在比赛结束一个小时之后才解出来的,认清了自己是菜鸡的事实。