leetcode
leetcode 2801 ~ 2850
下一个数

下一个数

难度:

标签:

题目描述

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. 1 <= num <= 2147483647
  2. 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位来表示整数,而不是其他位数?
在计算机中,通常使用32位来表示整数,其中有符号整数的最高位是符号位。在无符号整数的情况下,可以使用全部的32位来表示数值。这个解决方案中使用31位是为了保证处理的是一个没有符号的整数,避免涉及符号位带来的复杂性,同时确保结果在常用的整数表示范围内。如果使用更多的位数,可能会超出标准整数类型的范围,而使用更少的位数可能无法充分利用可用的数值范围。
🦆
在处理略大的数时,为什么选择从低位到高位寻找第一个'01'模式,并将其交换为'10',这种操作的数学依据是什么?
在二进制数中,低位权重较小,高位权重较大。当我们将低位的'01'交换为'10'时,实际上是将一个较小的权重(0)替换为一个较大的权重(1),并且这个改变尽可能地小,因为它发生在尽可能低的位数上。这样,数值会略微增大,而增加的幅度也是最小的,这正是寻找略大的数的目的。数学上来说,这是因为我们通过最小的位改变来实现数值的最小增加。
🦆
如果在整个二进制数组中都没有找到'01'或'10'模式,为什么直接返回-1?是否有其他可能的解决方案或替代方法?
在二进制数中,如果找不到'01'模式,意味着没有可能通过简单的位交换来获得一个略大的数,因为所有的'1'都在更高的位上,或者数值已经是连续的1后跟连续的0(如111...111000...000),这是一个递减或递增的极限情况。同理,找不到'10'模式意味着无法通过简单的位交换得到略小的数。在这种情况下,返回-1是表示没有可行的更大或更小的相邻数。理论上,除非增加额外的操作如位扩展或使用不同的数学方法,否则没有简单的替代方案来生成所需的略大或略小的数。

相关问题