《程序员面试金典(第6版)》面试题 05.04. 下一个数
创始人
2025-06-01 03:13:18

题目描述

下一个数。给定一个正整数,找出与其二进制表达式中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)。

总结

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

相关内容

热门资讯

重磅揭秘“桂林字牌真的有挂吗”... 您好,桂林字牌辅助软件这款游戏可以开挂的,确实是有挂的,需要了解加微【3696223】很多玩家在这款...
知识科普“海琼游戏脚本辅助修改... 【无需打开直接搜索微信;3696223】 操作使用教程:1.亲,实际上海琼游戏是可以开挂的,确实有挂...
玩家必看“独角兽其实是有透视软... 咨询加微信2780468,您好:独角兽这款游戏是可以开挂的,确实是有挂的,咨询加微信【2780468...
终于发现“湖南跑胡子究竟有没有... 亲,湖南跑胡子这款游戏可以开挂的,确实是有挂的,很多玩家在这款游戏中打牌都会发现很多用户的牌特别好,...
分享实测“微信链接斗牛能不能开... 咨询加微信2780468,你好,微信链接斗牛这款游戏可以开挂的,确实是有挂的,需要加微信【27804...