LeetCode 面试题 05.04. 下一个数
题目描述
题意分析
给定一个正整数
num，返回两个数：与它二进制中1的个数相同、但数值刚好更大的最小整数，以及刚好更小的最大整数；某一侧不存在时返回-1。“1 的个数相同”意味着重新排列现有的零和一，而不改变一的总数。数值比较由最高的不同位决定：求稍大的数，要尽量在低位把
0变为1；求稍小的数，则尽量在低位把1变为0，并用更低位的反向变化补回一的数量。返回值仍需处于正的 32 位有符号整数范围，因此只使用第
0..30位，不能把符号位置一。如果所有一已经集中在最低若干位，就没有一的数量相同且更小的正数；全部集中在最高若干位时，也没有范围内更大的同类数。
解法：交换最低可变相邻位并整理后缀
核心思路
[!blue]
求更大值时，从低位向高位找第一组相邻的
01，这里高位写在左侧。设高位编号为i，它下面的位还没有出现更低的01，所以这一后缀按从高到低看已经是若干个一后接若干个零，是给定一数量下的最大排列。只重排更低位无法继续增大，必须改变第i位或更高位；选择最低可行的i才能保持高位前缀尽量不变。把这组
01交换成10后，一的总数不变，结果已经更大。为了在这一前缀下取最小值，再把更低后缀中的一全部放到最低位。求更小值对称：找到第一组10，它下面已经是若干个零后接若干个一，无法仅靠重排继续减小；交换成01后，把余下的一放到后缀的最高位，使下降幅度尽可能小。代码用
dirs={0,1,0}统一这两种处理。p=0时(a,b)=(0,1)，寻找高低两位为01；p=1时(a,b)=(1,0)，寻找10。异或这两个不同的位完成交换后，在[0,i-2]中把低位排成b、高位排成a，分别对应更大值的最小后缀和更小值的最大后缀。双指针
j从最低位向上、k从后缀最高位向下移动：跳过低端已经是b的位，以及高端已经是a的位，剩下的一对错位值恰好不同，交换即可。指针外侧始终已经排好；交换后这两位会在下一轮被跳过，未处理区间不断缩小，直到两指针相遇或越过。每个方向一旦完成第一次交换和后缀整理，就得到保持高位前缀最多、低位又最接近原数的合法候选，可以立即停止。若扫描到位
30仍没有相应模式，这个方向不存在可表示的正数，保留-1。
解题步骤
- 答案初始化为
[-1, -1]，分别表示更大值与更小值尚未找到。- 对两个方向分别从
i = 1扫到30，检查第i位和第i-1位是否等于目标模式(a, b)。- 命中后用两次异或交换这两个不同的位。
- 在更低的后缀中用双指针交换放错位置的 0 和 1：求更大值时把 1 推向低位，求更小值时把 1 推向高位。
- 保存该方向答案并停止继续搜索；第一次命中就是变化幅度最小的位置。
若模式就在最低两位，待整理后缀为空，双指针循环自然跳过。两个方向都从原来的
num独立开始，不能把已经求得的较大值继续用于求较小值。
代码实现
// p=0 查找 01 得到更大值，p=1 查找 10 得到更小值。
class Solution {
public int[] findClosedNumbers(int num) {
int[] answer = {
-1,
-1
};
int[] dirs = {
0,
1,
0
};
for (int p = 0; p < 2; ++p) {
int a = dirs[p];
int b = dirs[p + 1];
int x = num;
for (int i = 1; i < 31; ++i) {
if ((x >> i & 1) == a && (x >> (i - 1) & 1) == b) {
x ^= 1 << i;
x ^= 1 << (i - 1);
int j = 0;
int k = i - 2;
while (j < k) {
while (j < k && (x >> j & 1) == b) {
++j;
}
while (j < k && (x >> k & 1) == a) {
--k;
}
if (j < k) {
x ^= 1 << j;
x ^= 1 << k;
}
}
answer[p] = x;
break;
}
}
}
return answer;
}
}
// p=0 查找 01 得到更大值，p=1 查找 10 得到更小值。
func findClosedNumbers(num int) []int {
answer := []int{
-1,
-1,
}
dirs := [3]int{
0,
1,
0,
}
for p := 0; p < 2; p++ {
a, b := dirs[p], dirs[p+1]
x := num
for i := 1; i < 31; i++ {
if x>>i&1 == a && x>>(i-1)&1 == b {
x ^= 1 << i
x ^= 1 << (i - 1)
j, k := 0, i-2
for j < k {
for j < k && x>>j&1 == b {
j++
}
for j < k && x>>k&1 == a {
k--
}
if j < k {
x ^= 1 << j
x ^= 1 << k
}
}
answer[p] = x
break
}
}
}
return answer
}
复杂度分析
- 时间复杂度：固定 32 位模型下为 $O(1)$。若位宽为
b，每个方向扫描一次，命中后只整理一次后缀并立即退出，因此总共为 $O(b)$，不是平方复杂度。- 空间复杂度：$O(1)$，只使用答案数组和若干下标、位值变量。
关键点总结
[!green]
- 这道题本质是二进制版本的“下一个排列 / 上一个排列”：先找最低可改变位置，再把后缀排成目标方向的极值。
- 求更大值是
01 → 10后让后缀最小；求更小值是10 → 01后让后缀最大。交换模式和后缀方向必须配套。- 交换与后缀重排都只移动现有位，因此始终保持一的数量不变。
易错点总结
[!yellow]
- 找到模式后只交换，不整理低位：只能保证结果位于目标方向，不能保证它是最接近的一个。
- 两个方向都把后缀排成最小：求更小值时结果会下降过多，不再是最大的较小值。
- 扫描到位 31 并执行
1 << 31：符号位被置 1，Java 结果变成负数，违反正整数约束。- 从
num + 1或num - 1逐个枚举并比较 bit count：在答案距离很远时需要大量无效尝试，完全没有利用位结构。- 把不存在的答案保留为 0：0 可能看似是较小值，但题目约定无解必须返回
-1。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 31. 下一个排列 | 中等 | 同样先找最靠右的可改变位置，再把后缀整理为最小值；本题还对称求前一个排列。 |
| 191. 位1的个数 | 简单 | 用位计数验证候选含有相同数量的1；本题进一步要求候选在数值上最近。 |