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.
解法
轮次模拟：每轮把当前选手按 score 排序，找出最大值；如果只有一个最大值就淘汰它(push 到结果)，多个并列则全部淘汰(按某固定顺序入结果)。最后剩下唯一选手附在结果末尾。每轮 O(n log n)，总共 n 轮，整体 O(n² log n)；对 OA 规模够用。
from typing import List
def determineEliminationOrder(results: List[List[str]]) -> List[str]:
if not results:
return []
rounds = results
eliminated: List[str] = []
remaining: dict[str, int] = {}
for entry in rounds[0]:
name, score = entry.rsplit(" ", 1)
remaining[name] = int(score)
round_idx = 0
while len(remaining) > 1:
if round_idx > 0:
new_scores: dict[str, int] = {}
for entry in rounds[round_idx]:
name, score = entry.rsplit(" ", 1)
if name in remaining:
new_scores[name] = int(score)
remaining = new_scores
max_score = max(remaining.values())
losers = [n for n, s in remaining.items() if s == max_score]
losers.sort()
for n in losers:
eliminated.append(n)
del remaining[n]
round_idx += 1
if round_idx >= len(rounds):
break
if remaining:
eliminated.extend(sorted(remaining.keys()))
return eliminatedimport java.util.*;
class Solution {
List<String> determineEliminationOrder(List<List<String>> results) {
List<String> eliminated = new ArrayList<>();
if (results.isEmpty()) return eliminated;
Map<String, Integer> remaining = new LinkedHashMap<>();
for (String entry : results.get(0)) {
int sp = entry.lastIndexOf(' ');
remaining.put(entry.substring(0, sp), Integer.parseInt(entry.substring(sp + 1)));
}
int roundIdx = 0;
while (remaining.size() > 1) {
if (roundIdx > 0) {
Map<String, Integer> next = new LinkedHashMap<>();
for (String entry : results.get(roundIdx)) {
int sp = entry.lastIndexOf(' ');
String name = entry.substring(0, sp);
if (remaining.containsKey(name)) {
next.put(name, Integer.parseInt(entry.substring(sp + 1)));
}
}
remaining = next;
}
int maxScore = Integer.MIN_VALUE;
for (int v : remaining.values()) maxScore = Math.max(maxScore, v);
List<String> losers = new ArrayList<>();
for (var e : remaining.entrySet()) if (e.getValue() == maxScore) losers.add(e.getKey());
Collections.sort(losers);
for (String n : losers) { eliminated.add(n); remaining.remove(n); }
roundIdx++;
if (roundIdx >= results.size()) break;
}
List<String> last = new ArrayList<>(remaining.keySet());
Collections.sort(last);
eliminated.addAll(last);
return eliminated;
}
}#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
class Solution {
public:
std::vector<std::string> determineEliminationOrder(std::vector<std::vector<std::string>>& results) {
std::vector<std::string> eliminated;
if (results.empty()) return eliminated;
std::unordered_map<std::string, int> remaining;
for (auto& entry : results[0]) {
auto sp = entry.rfind(' ');
remaining[entry.substr(0, sp)] = std::stoi(entry.substr(sp + 1));
}
size_t roundIdx = 0;
while (remaining.size() > 1) {
if (roundIdx > 0) {
std::unordered_map<std::string, int> next;
for (auto& entry : results[roundIdx]) {
auto sp = entry.rfind(' ');
std::string name = entry.substr(0, sp);
if (remaining.count(name)) next[name] = std::stoi(entry.substr(sp + 1));
}
remaining = next;
}
int maxScore = INT_MIN;
for (auto& [k, v] : remaining) maxScore = std::max(maxScore, v);
std::vector<std::string> losers;
for (auto& [k, v] : remaining) if (v == maxScore) losers.push_back(k);
std::sort(losers.begin(), losers.end());
for (auto& n : losers) { eliminated.push_back(n); remaining.erase(n); }
roundIdx++;
if (roundIdx >= results.size()) break;
}
std::vector<std::string> last;
for (auto& [k, v] : remaining) last.push_back(k);
std::sort(last.begin(), last.end());
for (auto& n : last) eliminated.push_back(n);
return eliminated;
}
};