LeetCode 面试题 05.04. 下一个数

一、题目

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

示例1:

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

示例2:

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

提示:

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

  点击此处跳转题目。

二、Java 题解

  看了一些题解后，分享一下我个人认为自己的较为简单易懂的代码。

  求大数和小数可以看做是进/退位运算，因此从右向左对二进制进行遍历，使用 ones 记录出现过 1 的次数。

2.1 求大数：

  求大数即进位，从左向右用指针 i（从 0 开始计数）对 num 进行判断，遇到 1 后第一次遇到 0 即停止。此时 i 指向 0，右方是连续的 1 串。将右方的连续 1 串进位（即 i 指向的 0 变为 1），之后重组剩余的 ones - 1 个 1（向右靠拢），得到最小的大数：

$$\begin{array}{l}{⟵}^i\\ 01\stackrel{i=5}{\overbrace{0}}\stackrel{ones=3}{\overbrace{111}}00\\ \\ \Downarrow +1\stackrel{i-ones个}{\overbrace{00}}\\ \\ 01\underline{1}00000\\ \\ \Downarrow +\stackrel{ones-1个}{\overbrace{11}}\\ \\ 011000\underline{1}\underline{1}\end{array}$$

2.2 求小数：

  求小数即退位，从左向右用指针 i 对 num 进行判断，遇到 0 后第一次遇到 1 即停止。此时 i 指向 1，右方是连续的 0 串。i 位退位（即 i 指向的 1 变为 0），之后重组剩余的 ones - 1 个 1（向左靠拢），得到最大的小数：

$$\begin{array}{l}{⟵}^i\\ 1\stackrel{i=6}{\overbrace{1}}00\stackrel{ones=4}{\overbrace{1111}}\\ \\ \Downarrow +1\\ \\ 110\underline{1}0000\\ \\ \Downarrow -1\stackrel{ones个}{\overbrace{0000}}\\ \\ 110\underline{0}0000\\ \\ \Downarrow -1\stackrel{i-ones-1个}{\overbrace{0}}\\ \\ 1\underline{0}\underset{i个}{\underbrace{\stackrel{ones+1个}{\overbrace{\underline{1}\underline{1}\underline{1}\underline{1}\underline{1}}}0}}\\ \end{array}$$

class Solution {public int[] findClosedNumbers(int num) {int[] ans = new int[] { -1, -1 };// 求大数int ones = 0;for (int i = 0; i < 31; i++) {               // i < 31 表示不考虑符号位if ((num & (1 << i)) != 0) ones++;       // 遇到 1 更新 onesif ((num & (1 << i)) == 0 && ones > 0) { // 遇到 1 后的第一个 0ans[0] = num + (1 << (i - ones)) + (1 << (ones - 1)) - 1;break;}}// 求小数ones = 0;for (int i = 0; i < 31; i++) {if ((num & (1 << i)) == 0) continue; // 忽略 0// 以下为遇到 1 的情况if (i > ones) {                      // i 比 ones 大，表示前面遇到了 0ans[1] = num - (1 << ones) - (1 << (i - ones - 1)) + 1;break;}ones++;                              // 更新 ones}return ans;}
}

• 时间：0 ms，击败 100.00% 使用 Java 的用户
• 内存：37.83 MB，击败 91.57% 使用 Java 的用户