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];
    }
}