Java C 题解 LeetCode 第k个数怎么找？

本文共计978个文字，预计阅读时间需要4分钟。

目录+主题要求+思路一：小根堆+Java+C+++思路二：多路归并[多指针]+Java+C+++Rust+总结+主题要求+思路一：小根堆+中文题目描述不够清晰，但题目本身可以发现，当x满足条件时，3x+

目录

• 题目要求
• 思路一：小根堆
• Java
• C++
• 思路二：多路归并
• Java
• C++
• Rust
• 总结

题目要求

思路一：小根堆

• 中文题目描述不太清晰，但其实由题目可以发现，当x满足条件时，3x、5x、7x分别也都满足条件。
• 将满足条件的数依次放入优先队列存放用于后续计算，由于每次要取待计算队列中最小的数x，所以定义小根堆：
  • 弹出x，计算3x、5x、7x并入队；
  • 用一个哈希表记录防止重复入队。
• 每次取数（pop）时进行计数，到第k次结束，当前队首即为答案。

Java

• 《学到了》
  • 1L也就是long型的数字1，那么同理1f就是float型，本质上都是相等的1。
  • 还有区分Long型和long型，前者是包装类，有函数可以调用。

class Solution { public int getKthMagicNumber(int k) { int[] nums = new int[]{3, 5, 7}; PriorityQueue<Long> que = new PriorityQueue<>(); Set<Long> set = new HashSet<>(); que.add(1L); set.add(1L); while (!que.isEmpty()) { long cur = que.poll(); if (--k == 0) return (int) cur; for (int x : nums) { // 3、5、7依次 if (!set.contains(x * cur)) { que.add(x * cur); set.add(x * cur); } } } return -1; } }

C++

class Solution { public: int getKthMagicNumber(int k) { int nums[3] = {3, 5, 7}; priority_queue<long, vector<long>, greater<long>> que; // 小根堆 unordered_set<long> set; que.push(1L); set.insert(1L); while (!que.empty()) { long cur = que.top(); que.pop(); if (--k == 0) return (int)cur; for (auto x : nums) { // 3、5、7依次 if (!set.count(x * cur)) { que.push(x * cur); set.insert(x * cur); } } } return -1; } };

思路二：多路归并

class Solution { public int getKthMagicNumber(int k) { int[] res = new int[k + 1]; res[1] = 1; for (int i3 = 1, i5 = 1, i7 = 1, idx = 2; idx <= k; idx++) { int r3 = res[i3] * 3, r5 = res[i5] * 5, r7 = res[i7] * 7; res[idx] = Math.min(r3, Math.min(r5, r7)); if (res[idx] == r3) i3++; if (res[idx] == r5) i5++; if (res[idx] == r7) i7++; } return res[k]; } }

• 时间复杂度：O(k)
• 空间复杂度：O(k)

class Solution { public: int getKthMagicNumber(int k) { int res[k + 1]; res[1] = 1; for (int i3 = 1, i5 = 1, i7 = 1, idx = 2; idx <= k; idx++) { int r3 = res[i3] * 3, r5 = res[i5] * 5, r7 = res[i7] * 7; res[idx] = min(r3, min(r5, r7)); if (res[idx] == r3) i3++; if (res[idx] == r5) i5++; if (res[idx] == r7) i7++; } return res[k]; } };

• 时间复杂度：O(k)
• 空间复杂度：O(k)

Rust

impl Solution { pub fn get_kth_magic_number(k: i32) -> i32 { let mut res = vec![0; (k + 1) as usize]; res[1] = 1; let (mut i3, mut i5, mut i7) = (1, 1, 1); for idx in 2..(k + 1) as usize { let (r3, r5, r7) = (res[i3] * 3, res[i5] * 5, res[i7] * 7); res[idx] = r3.min(r5.min(r7)); if (res[idx] == r3) { i3 += 1; } if (res[idx] == r5) { i5 += 1; } if (res[idx] == r7) { i7 += 1; } } res[k as usize] } }

• 时间复杂度：O(k)
• 空间复杂度：O(k)

总结

偷懒就不写rust的优先队列了……

是“丑数”的变种题目，题目描述有点问题（力扣日常、去看原文好理解很多），做过就会技巧性并不太强的题目~

以上就是Java C++题解 leetcode第k个数实例的详细内容，更多关于Java C++题解第k个数的资料请关注自由互联其它相关文章！