强整数【LC970】
给定三个整数 x 、 y 和 bound ，返回 值小于或等于 bound 的所有 强整数 组成的列表 。
如果某一整数可以表示为 xi + yj ，其中整数 i >= 0 且 j >= 0，那么我们认为该整数是一个 强整数 。
你可以按 任何顺序 返回答案。在你的回答中，每个值 最多 出现一次。
思路
数据范围不大，因此可以枚举i和j可能的组合，如果x或者y为1时，退出循环
- 实现
class Solution { public List<Integer> powerfulIntegers(int x, int y, int bound) { Set<Integer> set = new HashSet<>(); int i = 0, j = 0; int curX = 1; while (curX <= bound){ int curY = 1; while (curX + curY <= bound){ set.add(curX + curY); curY *= y; if (y == 1) break; } curX *= x; if (x == 1) break; } return new ArrayList<>(set); } }
复杂度
- 时间复杂度：O(log2bound)
- 空间复杂度：O(log2bound)
