Medium

题目描述

给定三个整数 x、y 和 bound，返回所有值小于或等于 bound 的强整数列表。

如果一个整数可以表示为 x^i + y^j 的形式（其中 i >= 0 和 j >= 0），那么这个整数就是强整数。

你可以按任何顺序返回答案。在你的答案中，每个值最多出现一次。

示例 1:

输入：x = 2, y = 3, bound = 10
输出：[2,3,4,5,7,9,10]
解释：
2 = 2^0 + 3^0
3 = 2^1 + 3^0
4 = 2^0 + 3^1
5 = 2^1 + 3^1
7 = 2^2 + 3^1
9 = 2^3 + 3^0
10 = 2^0 + 3^2

示例 2:

输入：x = 3, y = 5, bound = 15
输出：[2,4,6,8,10,14]

提示：

  • 1 <= x, y <= 100
  • 0 <= bound <= 10^6

解题思路

这道题要求找出所有满足 x^i + y^j <= bound 的强整数，其中 i >= 0, j >= 0。

核心思路：

  1. 使用双重循环枚举所有可能的 i 和 j 值
  2. 计算 x^i + y^j，如果结果小于等于 bound，则加入结果集
  3. 使用哈希集合去重，避免重复元素

关键优化点：

  • 当 x^i > bound 时，可以直接跳出外层循环，因为再增加 y^j 只会让结果更大
  • 当 x^i + y^j > bound 时，可以跳出内层循环，因为 y 的更高次幂只会让结果更大
  • 特殊处理 x = 1 或 y = 1 的情况，因为 1 的任何次幂都是 1

算法步骤：

  1. 创建哈希集合存储结果
  2. 外层循环枚举 x 的幂次，从 x^0 开始
  3. 内层循环枚举 y 的幂次，从 y^0 开始
  4. 计算当前的强整数值，如果超过 bound 则跳出
  5. 将有效值加入集合
  6. 转换为列表返回

代码实现

class Solution {
public:
    vector<int> powerfulIntegers(int x, int y, int bound) {
        unordered_set<int> result;
        
        for (int i = 1; i < bound; i *= x) {
            for (int j = 1; i + j <= bound; j *= y) {
                result.insert(i + j);
                if (y == 1) break;
            }
            if (x == 1) break;
        }
        
        return vector<int>(result.begin(), result.end());
    }
};

class Solution:
    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:
        result = set()
        
        i = 1
        while i < bound:
            j = 1
            while i + j <= bound:
                result.add(i + j)
                if y == 1:
                    break
                j *= y
            if x == 1:
                break
            i *= x
        
        return list(result)

public class Solution {
    public IList<int> PowerfulIntegers(int x, int y, int bound) {
        HashSet<int> result = new HashSet<int>();
        
        for (int i = 1; i < bound; i *= x) {
            for (int j = 1; i + j <= bound; j *= y) {
                result.Add(i + j);
                if (y == 1) break;
            }
            if (x == 1) break;
        }
        
        return new List<int>(result);
    }
}

var powerfulIntegers = function(x, y, bound) {
    const result = new Set();
    
    for (let i = 0; Math.pow(x, i) <= bound; i++) {
        for (let j = 0; Math.pow(x, i) + Math.pow(y, j) <= bound; j++) {
            result.add(Math.pow(x, i) + Math.pow(y, j));
            if (y === 1) break;
        }
        if (x === 1) break;
    }
    
    return Array.from(result);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(log_x(bound) × log_y(bound))
空间复杂度O(log_x(bound) × log_y(bound))

说明：

  • 时间复杂度：外层循环最多执行 log_x(bound) 次，内层循环最多执行 log_y(bound) 次
  • 空间复杂度：哈希集合最多存储 log_x(bound) × log_y(bound) 个不同的强整数

相关题目