【每日演算法Day 81】面試經典題：關於丑數，你真的理解為什麼這麼算嗎？

2020 年 3 月 27 日
筆記

題目鏈接

LeetCode 面試題 17.09. 第 k 個數[1]

題目描述

有些數的素因子只有 3，5，7，請設計一個演算法找出第 k 個數。注意，不是必須有這些素因子，而是必須不包含其他的素因子。例如，前幾個數按順序應該是 1，3，5，7，9，15，21。

示例1

輸入：  k = 5  輸出：  9

題解

這題和主站的LeetCode 264. 丑數 II是一個意思： https://leetcode-cn.com/problems/ugly-number-ii/

最直觀的想法就是，假設已經生成了個丑數，那麼我們把每個丑數都乘上 3，5，7，得到的結果中大於已經生成的所有丑數並且最小的那個就是下一個丑數。

但是這樣會產生很多重複的丑數，所以也可以用一個優先隊列，將已經生成的丑數從小到大保存下來。然後取出隊首最小的那個丑數，給它乘上 3，5，7，將新的三個數入隊，並且隊首的這個數出隊，這樣就不會再產生重複的數了。

上面這種方法已經可以過這道題了，但是還有更簡單的方法。

假設我們用一個數組來從小到大保存每一個丑數，那麼就保存著最小的丑數 1 。用三個指針分別指著最小的那個可以和相乘的丑數。那麼初始的時候都是 0，因為可以和三個因子相乘。

然後判斷三個數誰最小，哪個新丑數最小，就讓那個指針往後加 1 ，同時把那個新丑數作為下一個更大的丑數。

這麼做為什麼是對的呢？我們將數組寫成三行相同的形式：

那麼每一行的指針就表示了有資格和 3，5，7 相乘的最小的丑數。比如，那就說明只有才有資格和 3 相乘，生成新的丑數，而之前的早就和 3 乘過了，再乘就重複了沒有意義。但是可能這時，也就是還沒和 5 乘過，所以還是有資格乘 5 生成新的丑數的。

本質上相當於用了三個優先隊列，來存儲已生成的丑數。但是因為已生成的丑數是遞增的，所以就用普通的隊列也就是數組+指針就行了。每次三個隊首元素乘上對應因子比較一下，取最小的那個出隊，並且三個隊列都要入隊新丑數。

程式碼

c++

class Solution {  public:      int getKthMagicNumber(int k) {          vector<int> res(k, 1);          int idx3 = 0, idx5 = 0, idx7 = 0;          for (int i = 1; i < k; ++i) {              res[i] = min(res[idx3]*3, min(res[idx5]*5, res[idx7]*7));              if (res[i] == res[idx3]*3) idx3++;              if (res[i] == res[idx5]*5) idx5++;              if (res[i] == res[idx7]*7) idx7++;          }          return res[k-1];      }  };

python

class Solution:      def getKthMagicNumber(self, k: int) -> int:          res = [1] * k          idx3, idx5, idx7 = 0, 0, 0          for i in range(1, k):              res[i] = min(res[idx3]*3, res[idx5]*5, res[idx7]*7)              if res[i] == res[idx3]*3: idx3 += 1              if res[i] == res[idx5]*5: idx5 += 1              if res[i] == res[idx7]*7: idx7 += 1          return res[k-1]

參考資料

[1]

LeetCode 面試題 17.09. 第 k 個數: https://leetcode-cn.com/problems/get-kth-magic-number-lcci/

作者簡介：godweiyang，知乎同名，華東師範大學電腦系碩士在讀，方向自然語言處理與深度學習。喜歡與人分享技術與知識，期待與你的進一步交流~