题目描述

下一个数。给定一个正整数，找出与其二进制表达式中1的个数相同且大小最接近的那两个数（一个略大，一个略小）。

示例1:

• 输入：num = 2（或者0b10）
  输出：[4, 1] 或者（[0b100, 0b1]）

示例2:

• 输入：num = 1
  输出：[2, -1]

提示:

• num的范围在[1, 2147483647]之间；
  如果找不到前一个或者后一个满足条件的正数，那么输出 -1。

解题思路与代码

遇到这种题不要慌，仔细读题就好。

• 题目的意思是让我们找到这样两个两个数，一个数要比题目给定的那个数大，一个要比题目给定的那个数小。
• 还有两个前提条件就是，这两个数的二进制位中含1的数量，必须和给定的那个数的二进制位含有的1一样多。
• 并且，大于题目给定的数的这个数，必须刚刚好大于它，小于的那个数也得刚刚小于才行。
• 如果找不到大于的数，那就把大于它的那个数的值记作-1，放进返回数组中，小于的那个也相同。最后返回一个数组。

这道题需要你对位运算有一个基础的了解。如果会使用bitset数据结构，那更好，这道题会更加的简单。

我写了两篇文章，分别是介绍位运算与bitset这种数据结构的，基础不好的同学可以自行去点击链接去观看。

位运算基础知识：扫除盲点：教你理解位运算符
bitset数据结构基础知识：C++标准库类型，bitset类型

方法一： 使用bitset数据结构

我们要找到这样两个数，一个刚好比他大，一个刚好比它小。对于二进制的数而言：

• 比他大的那个数：遍历这个数的每一个二进制位 找到第一个 01 将它置换为 10 ，之后将置换后右侧的1与低位的0去做置换。最后的效果就是将置换后右侧的所有1都放到最右边，然后右侧的其余位置变为0
• 比他小的那个数：遍历这个数的每一个二进制位 找到第一个 10 将它置换为 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(log⁡n)O(\log n)O(logn)。
对于较大的数，代码中同样使用一个循环来遍历其二进制数中所有的位置，找到第一个出现的"01"，并进行相应的操作。因此，时间复杂度为O(log⁡n)O(\log n)O(logn)。
综上所述，代码的时间复杂度为O(log⁡n)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)。

总结

这道题不算一道特别难的题，但也不算简单。如果你对位运算稍微不熟悉一点了话，你也看不出这样的规律。其实代码也是不好去写的。掌握了这些知识后，代码才变得简单易懂了些。