面试题 17.09. 第 k 个数
链接:. – 力扣(LeetCode)
题解:堆和hash表
class Solution {
public:
int getKthMagicNumber(int k) {
if (k <= 0) {
return -1;
}
if (k == 1) {
return 1;
}
std::unordered_set table;
std::vector nums{3, 5, 7};
std::priority_queue<int64_t, std::vector, std::greater> que;
que.push(1);
table.insert(1);
int result = 1;
for (int i = 0; i < k; ++i) {
auto top = que.top();
result = top;
que.pop();
for (auto& num : nums) {
int64_t next_num = num * top;
if (table.find(next_num) != table.end()) {
continue;
}
que.push(next_num);
table.insert(next_num);
}
}
return result;
}
};