Leetcode 面試題 17.09. 第 k 個數

題目

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

示例 1:

• 思路一：使用優先隊列來儲存滿足條件的數，每次從堆頂彈出一個元素，将該元素x與3,5,7相乘後所得的數也是滿足題目要求的數，将其放入堆中，由于可能會出現重複元素，是以要去重後再放入堆中。

class Solution {
    public int getKthMagicNumber(int k) {
        PriorityQueue<Integer> q = new PriorityQueue<>();
        int tp = 0;
        q.add(1);
        while (k-- > 0) {
            tp = q.poll(); 
            if (tp * 3L < Integer.MAX_VALUE && !q.contains(tp * 3)) q.add(tp * 3);
            if (tp * 5L < Integer.MAX_VALUE && !q.contains(tp * 5)) q.add(tp * 5);
            if (tp * 7L < Integer.MAX_VALUE && !q.contains(tp * 7)) q.add(tp * 7);
        }
        return tp;
    }
}      

• 思路二：我門不用每次将3個乘積的數都放入堆中 ，再利用堆來彈出最小的數，通過分析可以知道，後面的數必然是前面的數 *3， * 5， *7後的結果，隻需要每次選出最小的一個結果便是目前的第i個數，用3個指針分别指向最開始的元素1，3個相乘的結果為3，5， 7， 這時候放入3為第2個元素，p3指針增加，若遇到相同的數時，每個指針都應該增加，這樣就避免了重複數出現的情況。

class Solution {
    public int getKthMagicNumber(int k) {
        int[] dp = new int[k + 1];
        int p3 = 1, p5 = 1, p7 = 1;
        dp[1] = 1;
        for (int i = 2; i <= k; i++) {
            dp[i] = Math.min(dp[p3] * 3, Math.min(dp[p5] * 5, dp[p7] * 7));
            if (dp[i] == dp[p3] * 3) p3++;
            if (dp[i] == dp[p5] * 5) p5++;
            if (dp[i] == dp[p7] * 7) p7++;
        }
        return dp[k];
    }
}