【优先队列, 动态规划, 多路归并】第 k 个数

题目

面试题 17.09. 第 k 个数

---

有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 1，3，5，7，9，15，21。

示例 1:

输入: k = 5

输出: 9

解题

方法一：优先队列 哈希表

思路

本题与 【优先队列, 动态规划, 多路归并】丑数 II 几乎相同。

方法一思路见：【优先队列, 动态规划, 多路归并】丑数 II - 方法一：小根堆(优先队列) 哈希表

代码

利用哈希表去重

class Solution {
    static final int[] FACTORS = {3, 5, 7};

    public int getKthMagicNumber(int k) {
        Queue<Long> minHeap = new PriorityQueue<>();
        Set<Long> seen = new HashSet<>();
        minHeap.offer(1L);
        seen.add(1L);
        long num = -1;
        while (k-- > 0) {
            num = minHeap.poll();
            for (int factor : FACTORS) {
                long newNum = num * factor;
                if (!seen.contains(newNum)) {
                    minHeap.offer(newNum);
                    seen.add(newNum);
                }
            }
        }
        return (int) num;
    }
}

不使用哈希表去重

class Solution {
    const int FACTORS[3] = {3, 5, 7};
    
public:
    int getKthMagicNumber(int k) {
        priority_queue<long long, vector<long long>, greater<long long>> min_heap;
        long long num = -1, prev = -1;
        min_heap.push(1L);
        while (k--) {
            num = min_heap.top();
            min_heap.pop();
            if (num == prev) {
                ++k;
                continue;
            }
            for (const long long& factor : FACTORS) {
                min_heap.push(num * factor);
            }
            prev = num;
        }
        return num;
    }
};

方法二：动态规划 / 多路归并

思路

本题与 【优先队列, 动态规划, 多路归并】丑数 II 几乎相同。

方法二思路见：【优先队列, 动态规划, 多路归并】丑数 II - 方法二：动态规划 / 多路归并

代码

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

class Solution {
public:
    int getKthMagicNumber(int k) {
        long long dp[k];
        dp[0] = 1;
        for (int p3 = 0, p5 = 0, p7 = 0, i = 1; i < k; ++i) {
            long long n3 = dp[p3] * 3, n5 = dp[p5] * 5, n7 = dp[p7] * 7;
            long long mn = min(n3, min(n5, n7));
            dp[i] = mn;
            if (mn == n3) ++p3;
            if (mn == n5) ++p5;
            if (mn == n7) ++p7;
        }
        return dp[k - 1];
    }
};