题目
我们把只包含质因子 2、3 和 5 的数称作丑数(Ugly Number)。求按从小到大的顺序的第 n 个丑数。
示例:
1 2 3
| 输入:n = 10 输出:12 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
|
附上链接:剑指offer.49题(LeetCode地址)
解题
思路
第一种,动态规划,三指针;
第二种,优先队列;
我这里使用第二种解题。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
| use std::collections::{BinaryHeap, HashMap}; use std::cmp::Reverse;
impl Solution { pub fn nth_ugly_number(n: i32) -> i64 { let mut idx: usize = 0; let mut out: i64 = 0; let mut bigHeap = BinaryHeap::new(); let mut repeat: HashMap<i64, bool> = HashMap::new();
bigHeap.push(Reverse::<i64>(1)); loop { if idx >= (n as usize) || bigHeap.len() == 0 { break; }
if let Some(Reverse::<i64>(mx)) = bigHeap.pop() {
if (mx * 2) > 0 && repeat.get(&(mx * 2)).is_none() { repeat.insert(mx * 2, true); bigHeap.push(Reverse::<i64>(mx * 2)); } if (mx * 3) > 0 && repeat.get(&(mx * 3)).is_none() { repeat.insert(mx * 3, true); bigHeap.push(Reverse::<i64>(mx * 3)); } if (mx * 5) > 0 && repeat.get(&(mx * 5)).is_none() { repeat.insert(mx * 5, true); bigHeap.push(Reverse::<i64>(mx * 5)); }
idx += 1; out = mx; } } return out; } }
|
总结
Rust优先队列
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
|
let mut b_heap = std::collections::BinaryHeap::new();
BinaryHeap<Reverse(T)>;
b_heap.push(T);
b_heap.pop() -> Option<T>;
b_heap.peek() -> Option<&T>;
b_heap.len() ->
|