首页 > 技术文章 > 程序员面试金典-面试题 05.04. 下一个数

silentteller 2020-03-09 14:10 原文

题目:

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

示例1:

输入:num = 2(或者0b10)
输出:[4, 1] 或者([0b100, 0b1])
示例2:

输入:num = 1
输出:[2, -1]
提示:

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

分析:

暴力解法,编写一个统计数字二进制1的个数,然后从给定数字开始遍历,判断当前数字和给定数字1的个数是否相同,这样便可以找到结果。

程序:

class Solution {
    public int[] findClosedNumbers(int num) {
        int[] res = new int[]{-1, -1};
        int numOne = countOne(num);
        for(int i = num+1; i <= 2147483647; ++i){
            int t = countOne(i);
            if(t == numOne){
                res[0] = i;
                break;
            }
        }
        for(int i = num-1; i >= 1; --i){
            int t = countOne(i);
            if(t == numOne){
                res[1] = i;
                break;
            }
        }
        return res;
    }
    private int countOne(int num){
        int count = 0;
        while(num != 0){
            if((num & 1) == 1)
                count++;
            num >>= 1;
        }
        return count;
    }
}

 

推荐阅读