Java C++题解 leetcode第k个数实例

题目要求

思路一:小根堆

  • 中文题目描述不太清晰,但其实由题目可以发现,当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;
 }
};

思路二:多路归并【多指针】

Java

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)

C++

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的优先队列了……

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

作者:AnjaVon

%s 个评论

要回复文章请先登录注册