题目难度: 中等
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
下一个数。给定一个正整数，找出与其二进制表达式中 1 的个数相同且大小最接近的那两个数（一个略大，一个略小）。
示例 1:
- 输入：num = 2（或者 0b10）
- 输出：[4, 1] 或者（[0b100, 0b1]）
示例 2:
- 输入：num = 1
- 输出：[2, -1]
提示:
- num 的范围在[1, 2147483647]之间；
- 如果找不到前一个或者后一个满足条件的正数，那么输出 -1。
题目思考
- 与原数最接近且 1 的个数相同的数有什么特点和规律?
解决方案
思路
- 根据题目描述, 很自然想到可以分别求略大和略小的数
- 求略大数:
- 例如 11001100 => 11010001
- 直观想法是, 我们可以从右向左遍历, 把最右边的 1 (从右数第 3 个数)填充到最接近且在其左边的 0 (从右数第 5 个数)那里, 然后遍历过程中遇到的 1 都给放到新的数的最低位上, 正如上面的转换那样
- 这样保证了新的数与原数字的 1 的个数相同, 且是大于原数字的最接近的数, 这是因为两者之间的数字都会将右侧的某些 0 变成 1, 不满足 1 个数相同这一条件
- 具体代码实现参考下面的 findLarger 函数, 每一步都有详细注释
- 求略小数:
- 例如 110011 => 101110
- 直观想法是, 我们可以从右向左遍历, 把右边存在 0 的最右边的 1 (从右数第 5 个数)与它右边的 0 (从右数第 4 个数)交换位置, 然后遍历过程中遇到的 1 (最右边的两个 1)都给放到新的 1 的右边, 正如上面的转换那样
- 这样保证了新的数与原数字的 1 的个数相同, 且是小于原数字的最接近的数, 这是因为两者之间的数字都会将右侧的某些 1 变成 0, 不满足 1 个数相同这一条件
- 具体代码实现参考下面的 findSmaller 函数, 每一步都有详细注释
复杂度
- 时间复杂度 O(logN): 只需遍历两次 num 的每一位
- 空间复杂度 O(1): 只使用了几个变量
代码
Python 3
class Solution:
def findClosedNumbers(self, num: int) -> List[int]:
# 找规律+位运算
mn, mx = 1, 2147483647
def findLarger(n):
# 从最低位开始找第1个1
# 然后继续向高位找, 记录1的个数ones, 直到再遇到0或到最高位
# 1. 如果达到最高位, 则说明找不到更大的数, 返回-1
# 2. 否则将遇到的0变成1, 然后之前遍历过的低位用000...111(ones-1个1, 因为改变的位已经将1个0转成1了, 所以这里ones要减1)代替
# 这样保证了得到的数与num的1的个数相同, 且是大于当前num的最接近的数
rightBits = 0 # 遍历的低位位数, 用于后面的左移恢复
# 从低位开始遍历, 直到找到第一个1
while n and n & 1 == 0:
n >>= 1
rightBits += 1
ones = 0 # 遍历的1的个数
# 继续遍历, 直到再次遇到0
while n and n & 1:
n >>= 1
rightBits += 1
ones += 1
# 将当前最低位的0变成1
n += 1
# 将右边部分清0, 并填充上000...111 (ones-1个1)
n = (n << rightBits) | ((1 << (ones - 1)) - 1)
# 如果得到的数字在32位正数范围内, 返回自身, 否则返回-1, 表示超出上限
return n if mn <= n <= mx else -1
def findSmaller(n):
# 从最低位开始找第1个0, 并记录此过程1的个数ones (如果没找到0, 则不可能存在更小的与num的1的个数相同的数, 直接返回-1)
# 然后继续向高位找, 直到再遇到1
# 将这个1变成0, 然后之前遍历过的低位用111...000(ones+1个1, 因为改变的位已经将1个1转成0了, 所以这里ones要加1)代替
# 这样保证了得到的数与num的1的个数相同, 且是小于当前num的最接近的数
rightBits = 0 # 遍历的低位位数, 用于后面的左移恢复
ones = 0
# 从低位开始遍历, 直到找到第一个0
while n and n & 1:
n >>= 1
rightBits += 1
ones += 1
if n == 0:
# 说明没找到0, 不可能存在更小的与num的1的个数相同的数, 直接返回-1
return -1
# 继续遍历, 直到再次遇到1
while n and n & 1 == 0:
n >>= 1
rightBits += 1
# 将当前最低位的1变成0
n -= 1
# 将右边部分清0, 并填充上111...000 (ones+1个1)
# 111...000可以通过先得到111, 然后左移剩余位数(即rightBits - ones - 1)得到
n = (n << rightBits) | (((1 << (ones + 1)) - 1) <<
(rightBits - ones - 1))
# 如果得到的数字在32位正数范围内, 返回自身, 否则返回-1, 表示超出上限
return n if mn <= n <= mx else -1
return [findLarger(num), findSmaller(num)] 大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号