下一个数
难度:
标签:
题目描述
Given a positive integer, print the next smallest and the next largest number that have the same number of 1 bits in their binary representation.
Example1:
Input: num = 2 (0b10) Output: [4, 1] ([0b100, 0b1])
Example2:
Input: num = 1 Output: [2, -1]
Note:
1 <= num <= 2147483647
- If there is no next smallest or next largest number, output -1.
代码结果
运行时间: 22 ms, 内存: 16.1 MB
/*
* 思路:
* 1. 使用Java Stream进行优化,通过IntStream查找满足条件的数。
*/
import java.util.stream.IntStream;
public class NextNumberStream {
public static int[] findNextNumbers(int num) {
int countOnes = Integer.bitCount(num);
int larger = IntStream.iterate(num + 1, i -> i + 1)
.filter(i -> Integer.bitCount(i) == countOnes)
.findFirst()
.orElse(-1);
int smaller = IntStream.iterate(num - 1, i -> i - 1)
.filter(i -> Integer.bitCount(i) == countOnes)
.filter(i -> i > 0)
.findFirst()
.orElse(-1);
return new int[]{larger, smaller};
}
public static void main(String[] args) {
int num = 2;
int[] result = findNextNumbers(num);
System.out.println("[" + result[0] + ", " + result[1] + "]");
}
}
解释
方法:
题解首先将给定的数转换成二进制数组形式,便于处理。接着,为找出略大的数,从低位到高位找到第一个'01'的模式并将其交换成'10',这会使得该数稍微变大。同时,为了保证增加最小,将所有位于该'01'模式之前的1都移到最低位。若找不到这样的模式,返回-1表示不存在这样的数。对于略小的数,寻找'10'模式并交换为'01',再将前面的1移动到该'10'模式的左边,保持数尽可能大但小于原数。最后,提供一个辅助函数来将二进制数组转换回整数。
时间复杂度:
O(1)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么这个解决方案中使用31位来表示整数,而不是其他位数?
▷🦆
在处理略大的数时,为什么选择从低位到高位寻找第一个'01'模式,并将其交换为'10',这种操作的数学依据是什么?
▷🦆
如果在整个二进制数组中都没有找到'01'或'10'模式,为什么直接返回-1?是否有其他可能的解决方案或替代方法?
▷