Java统计区间3的幂的代码如何用单个while循环替代双重循环优化效率

安全阿岳

2026-10-6

优化方案

原代码超时原因

时间复杂度过高：外层循环遍历区间所有整数，区间差为上亿时需执行上亿次，内层额外嵌套循环做除法运算，整体时间复杂度为*O((end-start)log₃n)，大输入下必然超时
浮点运算存在精度风险：使用double类型做除法判断3的幂，整数过大时浮点精度丢失会导致判断结果出错
特殊值处理逻辑有歧义：原代码中start==1时直接将count置为-1，而1本身是3⁰，若业务要求排除1可保留该逻辑，否则需要调整

单循环优化实现

直接从小到大生成所有3的幂次，判断是否落在[start, end]区间内即可。int范围内最多只有19个3的正整数幂（3¹⁹=1162261467，3²⁰已超过int最大值2147483647），因此最多执行20次循环，效率提升上万倍。

优化后的完整代码如下：

import java.util.*;

class PowerOf3 {
  
  public static void main(String[] args) {
    
    Scanner sc = new Scanner(System.in);
    
    System.out.print("Enter start and end: ");
    int start = sc.nextInt();
    int end = sc.nextInt();
    
    int ans = countNumbers(start, end);
    
    
    System.out.println("Answer = "+ans);
  }
  
  // Count the number of integers from start to
  // end (both inclusive) that are power of 3
  public static int countNumbers(int start, int end) {
    int count = 0;
    // 用long存储避免乘法溢出
    long power = 1;
    while (power <= end) {
        if (power >= start) {
            count++;
        }
        // 先判断下次乘3会不会溢出int范围，避免死循环
        if (power > Integer.MAX_VALUE / 3) {
            break;
        }
        power *= 3;
    }
    // 如果需要保留原代码排除1的逻辑，取消下方注释即可
    // if (start <= 1 && 1 <= end) {
    //     count--;
    // }
    return count;
  }
}