程序员面试金典 - 面试题 17.09. 第 k 个数（set优先队列/DP）

1. 题目

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

示例 1:
输入: k = 5
输出: 9

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/get-kth-magic-number-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

2.1 set “队列”

• 满足题目要求的数只能乘以3、5、7
• 用set，有序，可以去重、当做优先队列
• 不断的出队begin(), 且把 begin() 的 3,5,7倍数插入队列

class Solution {
public:
    int getKthMagicNumber(int k) {
    	set<long> q;//可以看做小顶堆
    	long ans;
    	q.insert(1);
    	while(k--)
    	{
    		ans = *q.begin();
    		q.erase(q.begin());
    		q.insert(ans*3);
    		q.insert(ans*5);
    		q.insert(ans*7);
    	}
    	return ans;
    }
};

2.2 动态规划

• 参考 LeetCode 263. 丑数 && 264. 丑数 II（DP）

自己画一下就明白了，比较潦草，见谅

class Solution {
public:
    int getKthMagicNumber(int k) {
        vector<long> dp(k+1,0);
        dp[1] = 1;
        int i3=1, i5=1, i7=1;
        for(int i = 2; i <= k; i++)
        {
        	dp[i] = min(dp[i3]*3, min(dp[i5]*5, dp[i7]*7));
        	if(dp[i3]*3 == dp[i])
        		i3++;
        	if(dp[i5]*5 == dp[i])
        		i5++;
        	if(dp[i7]*7 == dp[i])
        		i7++;
        }
        return dp[k];
    }
};

0 ms 6.1 MB