范围在[1, 10^9]的二的指数的数就那么多,我们全部枚举即可。转化成string的时候sort一遍当做key存到hash set当中,对于输入的数我们也sort然后去hash set里找即可。hash set我们只initialize一次,存成static即可。如果输入的数的范围为N,2的指数有log N个,十进制的表示有log N位,sort的话时间复杂度O(log N * log log N)建set的时间复杂度就为O(log N * log N * log log N)。查询的时间复杂度就为sort的复杂度O(log N * log log N)。代码如下:
No comments:
Post a Comment