LeetCode 面试题 05.04. 下一个数

2026-03-28 HGNULB 约 6 分钟

文章信息 3 个分类 1 个标签

分类

题目描述

✅ 面试题 05.04. 下一个数

题意分析

给定一个正整数 num，返回两个数：与它二进制中 1 的个数相同、但数值刚好更大的最小整数，以及刚好更小的最大整数；某一侧不存在时返回 -1。

“1 的个数相同”意味着只能重新排列现有的 0 和 1，不能增加或删除 1。数值大小由高位优先决定：想得到稍大的数，要找到最低的一组 01（高位在左）改成 10；想得到稍小的数，则找最低的一组 10 改成 01。交换位置之后，还要把更低位重新排成该方向上的最优形态。

返回值必须仍是正的 32 位有符号整数，所以搜索只到位 30，不能把符号位翻成 1。全是低位连续 1、且再向上移动会越过正数范围时，较大值不存在；只有一个 1 且已在最低位时，较小值不存在。

解法：交换最低可变相邻位并整理后缀

核心思路

从低位向高位找第一个可交换模式，是“变化尽量小”的关键。求更大值时，最低的 01 → 10 是最靠右、影响最小的一次增大；交换后，为了让结果尽可能小，应把其下方所有 1 尽量放到低位。求更小值完全对称：最低的 10 → 01 造成最小幅度的下降，再把下方的 1 尽量放到高位，使结果尽可能大。

代码用 dirs = {0, 1, 0} 统一两个方向。p = 0 时 a = 0、b = 1，寻找 01 得到更大值；p = 1 时寻找 10 得到更小值。找到后先异或两位完成交换，再用双指针整理区间 [0, i-2]：左指针跳过已经放对的 b，右指针跳过已经放对的 a，其余成对交换。

不变量是：第一次命中的位置 i 以下，所有更低的相邻位都无法单独完成目标方向的变化；因此必须在 i 处改变。改变之后，高于 i 的前缀保持不动，后缀按目标方向取极值，所得结果自然是距离 num 最近的那个。

解题步骤

答案初始化为 [-1, -1]，分别表示更大值与更小值尚未找到。

对两个方向分别从 i = 1 扫到 30，检查第 i 位和第 i-1 位是否等于目标模式 (a, b)。

命中后用两次异或交换这两个不同的位。

在更低的后缀中用双指针交换放错位置的 0 和 1：求更大值时把 1 推向低位，求更小值时把 1 推向高位。

保存该方向答案并停止继续搜索；第一次命中就是变化幅度最小的位置。

以 num = 10 = 0b1010 为例。求更大值时，最低可用模式是位 2..1 的 01，交换成 10 得 1100，即 12；求更小值时，最低两位就是 10，交换成 01 得 1001，即 9。两者都含两个 1，答案为 [12, 9]。

代码实现

// 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], 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, 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 位整数下最多扫描并整理常数个 31 位，故为 $O(1)$；推广到 b 位整数是 $O(b)$。

空间复杂度：$O(1)$，只使用答案数组和若干下标、位值变量。

关键点总结

这道题本质是二进制版本的“下一个排列 / 上一个排列”：先找最低可改变位置，再把后缀排成目标方向的极值。

求更大值是 01 → 10 后让后缀最小；求更小值是 10 → 01 后让后缀最大。交换模式和后缀方向必须配套。

面试时最好用 10(1010) → 12(1100)、9(1001) 同时演示两个方向，比背位运算公式更容易证明正确性。

追问若允许 64 位整数，算法不变，但循环上界、常量类型与移位字面量都必须同步改为 64 位。

易错点总结

找到相邻模式后只交换，不整理低位：num = 0b10110 求更大值时会得到一个可行数，却不一定是最小的更大值；后缀中的 1 必须全部压到最低位。

两个方向都把后缀排成最小：求更小值时结果会下降过多，不再是最大的较小值。

扫描到位 31 并执行 1 << 31：符号位被置 1，Java 结果变成负数，违反正整数约束。

从 num + 1 或 num - 1 逐个枚举并比较 bit count：在答案距离很远时需要大量无效尝试，完全没有利用位结构。

把不存在的答案保留为 0：0 可能看似是较小值，但题目约定无解必须返回 -1。

相似题目

题目	难度	考察点
31. 下一个排列	中等	十进制序列中同样先找最低可变位置，再整理后缀
191. 位1的个数	简单	统计 1 的数量，可用于校验枚举解但不是本题最优解
面试题 05.06. 整数转换	简单	异或定位不同位，再统计位数
面试题 05.07. 配对交换	简单	用掩码批量移动奇偶位