下一个数。给定一个正整数,找出与其二进制表达式中1的个数相同且大小最接近的那两个数(一个略大,一个略小)。
示例1:
示例2:
提示:
遇到这种题不要慌,仔细读题就好。
这道题需要你对位运算有一个基础的了解。如果会使用bitset数据结构,那更好,这道题会更加的简单。
我写了两篇文章,分别是介绍位运算与bitset这种数据结构的,基础不好的同学可以自行去点击链接去观看。
位运算基础知识:扫除盲点:教你理解位运算符
bitset数据结构基础知识:C++标准库类型,bitset类型
我们要找到这样两个数,一个刚好比他大,一个刚好比它小。对于二进制的数而言:
01
将它置换为 10
,之后将置换后右侧的1与低位的0去做置换。最后的效果就是将置换后右侧的所有1都放到最右边,然后右侧的其余位置变为010
将它置换为 01
,之后将置换后右侧的0与低位的1去做置换。最后的效果就是将置换后右侧的所有0都放到最右边,然后右侧的其余位置变为1。这个同学们去拿纸笔演草一下就知道,这个逻辑是正确的。剩下我们只需要用代码去实现就好了。
剩下的注释我会写在具体的实现中去:
代码如下:
class Solution {
public:vector findClosedNumbers(int num) {bitset<32> small(num); //存较小的那个数的二进制序列bitset<32> big(num); //存较大的那个数的二进制序列int s = -1;//注意,int的最高位为符号位,所以我们这里直接少算一位。for(int i = 1; i < 31; ++i){ //找到第一个 10 将它置换为 01,之后 将右侧的1全部都放到最左边,右侧剩余的位置置为0if(small[i] == 1 && small[i-1] == 0){//交换他们的位置small.flip(i);small.flip(i-1);//设置两个指针,一个在最右侧,一个在置换后右侧一位。for(int left = 0,right = i - 2 ; left < right;){while(left < right && small[left] == 0) ++left; //找到最右侧的0while(left < right && small[right] == 1) --right;//找到最左侧的1//交换他们彼此的位置small.flip(left);small.flip(right);}s = (int)small.to_ulong();break;}}int b = -1;for(int i = 0; i < 31; ++i){if(big[i] == 0 && big[i - 1] == 1){big.flip(i);big.flip(i-1);for(int left = 0,right = i - 2; left < right;){while(left < right && big[left] == 1) ++left;while(left < right && big[right] == 0) --right;big.flip(left);big.flip(right);}b = (int)big.to_ulong();break;}}return {b,s};}
};
时间复杂度分析:
对于较小的数,代码中使用一个循环来遍历其二进制数中所有的位置,找到第一个出现的"10",并进行相应的操作。因此,时间复杂度为O(logn)O(\log n)O(logn)。
对于较大的数,代码中同样使用一个循环来遍历其二进制数中所有的位置,找到第一个出现的"01",并进行相应的操作。因此,时间复杂度为O(logn)O(\log n)O(logn)。
综上所述,代码的时间复杂度为O(logn)O(\log n)O(logn)。
空间复杂度分析:
空间复杂度主要取决于两个std::bitset对象的空间占用,由于本题中输入的整数不超过231−12^{31}-1231−1,因此这两个std::bitset对象的大小都为32,即占用32×132 \times 132×1个字节的空间。因此,空间复杂度为O(1)O(1)O(1)。
综上所述,代码的空间复杂度为O(1)O(1)O(1)。
这道题不算一道特别难的题,但也不算简单。如果你对位运算稍微不熟悉一点了话,你也看不出这样的规律。其实代码也是不好去写的。掌握了这些知识后,代码才变得简单易懂了些。