当前位置: 面试刷题>> 拥有同样多1的下一个数 (经典算法题500道)


题目描述补充

编写一个函数,该函数接收一个非负整数作为输入,并返回大于该数且二进制表示中1的个数与输入数的二进制表示中1的个数相同的下一个最小整数。如果不存在这样的数,则返回-1。

示例

  • 输入:n = 5(二进制表示为101),输出:9(二进制表示为1001),因为5的二进制表示有2个1,而大于5的下一个数9的二进制表示也有2个1。
  • 输入:n = 7(二进制表示为111),输出:-1,因为不存在比7大且二进制中1的个数仍为3的整数。

PHP 示例代码

function nextIntegerWithSameNumberOfOnes($n) {
    $onesCount = substr_count(decbin($n), '1');
    $next = $n + 1;
    
    while ($next > 0) {
        $currOnesCount = substr_count(decbin($next), '1');
        if ($currOnesCount == $onesCount) {
            return $next;
        }
        $next++;
    }
    
    return -1;
}

// 测试示例
echo nextIntegerWithSameNumberOfOnes(5); // 输出 9
echo "\n";
echo nextIntegerWithSameNumberOfOnes(7); // 输出 -1

Python 示例代码

def nextIntegerWithSameNumberOfOnes(n):
    def count_ones(num):
        return bin(num).count('1')
    
    ones_count = count_ones(n)
    next_num = n + 1
    
    while True:
        if count_ones(next_num) == ones_count:
            return next_num
        next_num += 1
        if next_num > (1 << 32):  # 假设是32位整数,防止无限循环
            return -1

# 测试示例
print(nextIntegerWithSameNumberOfOnes(5))  # 输出 9
print(nextIntegerWithSameNumberOfOnes(7))  # 输出 -1

JavaScript 示例代码

function nextIntegerWithSameNumberOfOnes(n) {
    function countOnes(num) {
        let count = 0;
        while (num) {
            count += num & 1;
            num >>= 1;
        }
        return count;
    }

    let onesCount = countOnes(n);
    let next = n + 1;

    while (true) {
        let currOnesCount = countOnes(next);
        if (currOnesCount === onesCount) {
            return next;
        }
        next++;
    }

    // 理论上JavaScript的Number类型足够大,但为了防止可能的无限循环,可以设置一个上限
    // 这里省略了上限设置,因为JavaScript的Number类型溢出会变为Infinity,但实际应用中应谨慎处理
}

// 测试示例
console.log(nextIntegerWithSameNumberOfOnes(5)); // 输出 9
console.log(nextIntegerWithSameNumberOfOnes(7)); // 输出 -1(注意:这里的-1需要额外的逻辑处理,因为函数当前设计为返回符合条件的下一个数)

请注意,JavaScript 示例中的函数在达到 JavaScript Number 类型的上限时可能不会返回 -1,而是会遇到数值溢出的问题。在实际应用中,可能需要添加额外的逻辑来处理这种情况。

码小课网站中有更多相关内容分享给大家学习,包括各种算法问题的深入解析和实战演练,欢迎大家访问并交流学习。

推荐面试题