题目描述
有些数的素因子只有 3,5,7,请设计一个算法找出第 k 个数。注意,不是必须有这些素因子,而是必须不包含其他的素因子。例如,前几个数按顺序应该是 1,3,5,7,9,15,21。
示例 1:
输入: k = 5 输出: 9
核心思想:动态规划
因为DP在时间和空间上都能达到最优,即O(N);
解题思路:在此称3, 5, 7倍数的素数是丑数(非严格意义上的丑数,在此只是为了便于描述)。那么对于第K个素数,其一定是f(K) = min(某个素数的3倍,某个素数的5倍,某个素数的7倍)。
举例说明如下所示:
dp[0] = 1; p3 = 0, p5 = 0, p7 = 0; dp[1] = ( dp[p3]*3, dp[p5]*5, dp[p7]*7 ) = ( 3, 5, 7 ) --> 3; p3 = 1, p5 = 0, p7 = 0; dp[2] = ( dp[p3]*3, dp[p5]*5, dp[p7]*7 ) = ( 9, 5, 7 ) --> 5; p3 = 1, p5 = 1, p7 = 0; dp[3] = ( dp[p3]*3, dp[p5]*5, dp[p7]*7 ) = ( 9, 15, 7 ) --> 7; p3 = 1, p5 = 1, p7 = 1; dp[4] = ( dp[p3]*3, dp[p5]*5, dp[p7]*7 ) = ( 9, 15, 21 ) --> 9; p3 = 2, p5 = 1, p7 = 1; dp[5] = ( dp[p3]*3, dp[p5]*5, dp[p7]*7 ) = ( 15, 15, 21 ) --> 15; p3 = 3, p5 = 2, p7 = 1; dp[6] = ( dp[p3]*3, dp[p5]*5, dp[p7]*7 ) = ( 21, 25, 21 ) --> 21; p3 = 4, p5 = 2, p7 = 2; dp[7] = ( dp[p3]*3, dp[p5]*5, dp[p7]*7 ) = ( 27, 25, 35 ) --> 25; p3 = 4, p5 = 3, p7 = 2; dp[8] = ( dp[p3]*3, dp[p5]*5, dp[p7]*7 ) = ( 27, 35, 35 ) --> 27; p3 = 5, p5 = 3, p7 = 2; .....
解题步骤:
- 定义一个数组,该数组按照顺序存放整个过程中产生的素数(K个素数),由题意可知,第一个元素为1;
- 然后再定义三个指针p3,p5,p7:p3指向的数字永远乘3,p5指向的数字永远乘5,p7指向的数字永远乘7;
- 从dp[p3]*3 , dp[p5]*5 , dp[p7]*7 选取最小的一个数字,作为新的素数,并移动对应的指针;
- 重复执行上一步。
这里基于的一个事实是,素数的数列是递增的,当p5指针在当前位置时,后面的数乘以5必然比前面的数乘以5大,所以下一个数必然是先考虑前面的数乘以5。p3,p7同理,所以才可以使用指针。
具体实现代码如下:
class Solution { public: int getKthMagicNumber(int k) { vector<int> numArray; numArray.reserve(k); numArray[0] = 1; int p3=0,p5=0,p7=0; for(int i=1;i<k;++i) { numArray[i] = min(min(numArray[p3]*3,numArray[p5]*5),numArray[p7]*7); if(numArray[i] == numArray[p3]*3) ++p3; if(numArray[i] == numArray[p5]*5) ++p5; if(numArray[i] == numArray[p7]*7) ++p7; } return numArray[k-1]; } };
复杂度分析:
- 时间复杂度:执行K次循环,因此时间复杂度为O(N);
- 空间复杂度:整个处理过程中会保存K个素数,因此空间复杂度为O(N)。
AC结果:
c/c++开发分享LeetCode 刷题 [C++] [面试题 17.09]. 第 k 个数 (动态规划 + 三指针)地址:https://blog.csdn.net/weixin_44953262/article/details/111026383
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/596415.html