Java?C++題解?leetcode第k個(gè)數(shù)實(shí)例
題目要求
思路一:小根堆
- 中文題目描述不太清晰,但其實(shí)由題目可以發(fā)現(xiàn),當(dāng)x滿足條件時(shí),3x、5x、7x分別也都滿足條件。
- 將滿足條件的數(shù)依次放入優(yōu)先隊(duì)列存放用于后續(xù)計(jì)算,由于每次要取待計(jì)算隊(duì)列中最小的數(shù)x,所以定義小根堆:
- 彈出x,計(jì)算3x、5x、7x并入隊(duì);
- 用一個(gè)哈希表記錄防止重復(fù)入隊(duì)。
- 每次取數(shù)(
pop
)時(shí)進(jìn)行計(jì)數(shù),到第k次結(jié)束,當(dāng)前隊(duì)首即為答案。
Java
- 《學(xué)到了》
1L
也就是long
型的數(shù)字1,那么同理1f
就是float
型,本質(zhì)上都是相等的1。- 還有區(qū)分
Long
型和long
型,前者是包裝類,有函數(shù)可以調(diào)用。
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]; } }
- 時(shí)間復(fù)雜度:O(k)
- 空間復(fù)雜度: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]; } };
- 時(shí)間復(fù)雜度:O(k)
- 空間復(fù)雜度: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] } }
- 時(shí)間復(fù)雜度:O(k)
- 空間復(fù)雜度:O(k)
總結(jié)
偷懶就不寫rust
的優(yōu)先隊(duì)列了……
是“丑數(shù)”的變種題目,題目描述有點(diǎn)問(wèn)題(力扣日常、去看原文好理解很多),做過(guò)就會(huì)技巧性并不太強(qiáng)的題目~
以上就是Java C++題解 leetcode第k個(gè)數(shù)實(shí)例的詳細(xì)內(nèi)容,更多關(guān)于Java C++題解第k個(gè)數(shù)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
c++實(shí)現(xiàn)加載so動(dòng)態(tài)庫(kù)中的資源
下面小編就為大家?guī)?lái)一篇c++實(shí)現(xiàn)加載so動(dòng)態(tài)庫(kù)中的資源。小編覺(jué)得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2016-12-12OpenCV提取圖像中圓線上的數(shù)據(jù)具體流程
在對(duì)圖像進(jìn)行處理時(shí),經(jīng)常會(huì)要提取出圖像中某條直線、圓線或者ROI區(qū)域內(nèi)的感興趣數(shù)據(jù),進(jìn)行重點(diǎn)關(guān)注。本文主要介紹了利用OpenCV獲取圖像中圓線上的數(shù)據(jù),需要的可以參考一下2021-11-11C語(yǔ)言使用stdlib.h庫(kù)函數(shù)的二分查找和快速排序的實(shí)現(xiàn)代碼
以下是對(duì)C語(yǔ)言使用stdlib.h庫(kù)函數(shù)的二分查找和快速排序的實(shí)現(xiàn)代碼進(jìn)行了詳細(xì)的介紹,需要的朋友可以過(guò)來(lái)參考下。希望對(duì)大家有所幫助2013-10-10C語(yǔ)言實(shí)現(xiàn)數(shù)組元素排序方法詳解
這篇文章主要為大家介紹了C語(yǔ)言算法練習(xí)中數(shù)組元素排序的實(shí)現(xiàn)方法,文中的示例代碼講解詳細(xì),對(duì)我們學(xué)習(xí)C語(yǔ)言有一定幫助,需要的可以參考一下2023-02-02你只用do-while來(lái)實(shí)現(xiàn)循環(huán)?太浪費(fèi)了
這篇文章主要介紹了你只用do-while來(lái)實(shí)現(xiàn)循環(huán)?太浪費(fèi)了,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-12-12ShellExecute函數(shù)用法的實(shí)例代碼
ShellExecute函數(shù)用法的實(shí)例代碼,需要的朋友可以參考一下2013-03-03