如何高效统计int(a)至int(b)区间内的幸运数？Java性能优化求助

嘿，这个问题其实很好解决——根本不用遍历整个区间！核心思路是先生成所有可能的int范围内的幸运数，然后直接统计其中落在int(a)到int(b)区间里的数量就行。毕竟幸运数的总数太少了，int范围内满打满算也就几百个，生成它们的成本几乎可以忽略不计，绝对能在1秒内搞定。

为什么这个思路高效？ #

如果直接遍历[a,b]区间，当a和b差距极大时（比如从1到2^31-1），要处理20多亿个数字，这肯定慢到离谱。但幸运数的生成逻辑很简单：每位只能是3或7，我们可以按位数迭代/递归生成所有可能的组合，直到数值超过int的最大值停止。

int的最大值是2147483647，所以最大的有效幸运数是77777777（8位），9位的幸运数最小是333333333，已经超过int上限了。算下来总共有2+4+8+16+32+64+128+256=510个幸运数，处理这么点数据完全没压力。

Java实现方案 #

我们可以提前生成所有int范围内的幸运数并排序，之后用二分查找快速定位区间边界，统计符合条件的数量。

代码实现（递归生成+二分查找） #

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class LuckyNumberCounter {
    // 提前生成并排序所有int范围内的幸运数
    private static final List<Integer> ALL_LUCKY_NUMBERS;

    static {
        ALL_LUCKY_NUMBERS = new ArrayList<>();
        generateLuckyNumbers(0);
        Collections.sort(ALL_LUCKY_NUMBERS);
    }

    // 递归生成所有幸运数
    private static void generateLuckyNumbers(int current) {
        if (current > 0) {
            ALL_LUCKY_NUMBERS.add(current);
        }
        // 生成下一位为3的数字，判断是否溢出（int溢出会变负数）
        int next3 = current * 10 + 3;
        if (next3 > 0) {
            generateLuckyNumbers(next3);
        }
        // 生成下一位为7的数字
        int next7 = current * 10 + 7;
        if (next7 > 0) {
            generateLuckyNumbers(next7);
        }
    }

    // 统计区间内的幸运数数量
    public static int countLuckyInRange(int a, int b) {
        // 找到第一个 >= a 的元素索引
        int leftIdx = Collections.binarySearch(ALL_LUCKY_NUMBERS, a);
        if (leftIdx < 0) {
            leftIdx = -leftIdx - 1;
        }

        // 找到最后一个 <= b 的元素索引
        int rightIdx = Collections.binarySearch(ALL_LUCKY_NUMBERS, b);
        if (rightIdx < 0) {
            rightIdx = -rightIdx - 2;
        }

        // 计算有效数量，注意边界判断
        return rightIdx >= leftIdx ? rightIdx - leftIdx + 1 : 0;
    }

    public static void main(String[] args) {
        int a = 7;
        int b = 33777;
        System.out.println(countLuckyInRange(a, b)); // 输出区间内的幸运数数量
    }
}

代码说明 #

1. 提前生成：静态代码块在类加载时就生成所有幸运数并排序，后续调用统计方法时无需重复生成，效率拉满。
2. 溢出判断：递归生成时通过next3 > 0判断是否溢出，避免生成无效的负数。
3. 二分查找：用Collections.binarySearch快速定位区间的左右边界，时间复杂度为O(log n)（n为幸运数总数，仅几百），几乎瞬间完成统计。

可选：BFS生成方式 #

如果你觉得递归不够直观，也可以用队列实现BFS生成：

private static List<Integer> generateLuckyNumbers() {
    List<Integer> result = new ArrayList<>();
    Queue<Integer> queue = new LinkedList<>();
    queue.add(3);
    queue.add(7);

    while (!queue.isEmpty()) {
        int num = queue.poll();
        result.add(num);
        int next3 = num * 10 + 3;
        if (next3 > 0) queue.add(next3);
        int next7 = num * 10 + 7;
        if (next7 > 0) queue.add(next7);
    }
    Collections.sort(result);
    return result;
}

方案优势 #

不管a和b的范围多大，这个方案的处理时间都是恒定的——只需要处理几百个幸运数，完全不会出现遍历大区间的性能问题，绝对满足耗时小于1秒的要求。

内容的提问来源于stack exchange，提问作者user14191409