Given an array and a value k, find
Example 1
Input:
arr = [11, 121, 10]
k = 11Output:
2Explanation:
解法
题意是数组中是 k 的整数次幂的元素个数。预先生成 k 的所有幂(1, k, k², ...)放进集合，然后对每个元素查询是否在集合里。注意 k=1 的特例(只有 1 是 1 的幂)。时间 O(n + log_k(max))，空间 O(log_k(max))。
from typing import List
def countPowersOfK(arr: List[int], k: int) -> int:
if k <= 0:
return 0
if k == 1:
return sum(1 for x in arr if x == 1)
powers = set()
p = 1
cap = max(arr) if arr else 0
while p <= cap:
powers.add(p)
if p > cap // k:
break
p *= k
return sum(1 for x in arr if x in powers)import java.util.*;
class Solution {
int countPowersOfK(int[] arr, int k) {
if (k <= 0) return 0;
if (k == 1) {
int c = 0;
for (int x : arr) if (x == 1) c++;
return c;
}
int cap = 0;
for (int x : arr) cap = Math.max(cap, x);
Set<Long> powers = new HashSet<>();
long p = 1;
while (p <= cap) {
powers.add(p);
if (p > cap / k) break;
p *= k;
}
int count = 0;
for (int x : arr) if (powers.contains((long) x)) count++;
return count;
}
}#include <vector>
#include <unordered_set>
#include <algorithm>
class Solution {
public:
int countPowersOfK(std::vector<int>& arr, int k) {
if (k <= 0) return 0;
if (k == 1) {
int c = 0;
for (int x : arr) if (x == 1) c++;
return c;
}
long long cap = 0;
for (int x : arr) cap = std::max(cap, (long long) x);
std::unordered_set<long long> powers;
long long p = 1;
while (p <= cap) {
powers.insert(p);
if (p > cap / k) break;
p *= k;
}
int count = 0;
for (int x : arr) if (powers.count(x)) count++;
return count;
}
};Given the competition results, determine the elimination order. For example:
Input:
[["Tom 20", "Sam 10"], ["Sam 20", "Tom 10"]]
In the first round, Tom takes the longest time and gets eliminated. In the second round, only Sam remains, so their score is valid and added to the output list.
Output:
["Tom", "Sam"]
Edge case: If scores are tied, all tied contestants are eliminated simultaneously.
Example 1
Input:
results = [["Tom 20", "Sam 10"], ["Sam 20", "Tom 10"]]Output:
["Tom", "Sam"]Explanation: In the first round, Tom takes the longest time and gets eliminated. In the second round, only Sam remains, so their score is valid and added to the output list.
解锁全部 1 道题的解法
题面你已经看到了 — 解法 + 三语代码 + 复杂度推导 + 边界讨论, Pro 解锁.
- 📚1000+ 道真实北美 OA, Python / Java / C++ 三语题解
- 📊个人 dashboard + 进度可视化 + 14 天活跃图
- 📝题目笔记跨设备同步 + 个人复盘库
- 🔓随时取消下次续费, Stripe Customer Portal 自助管理