欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

LeetCode 刷题 [C++] [面试题 17.09]. 第 k 个数 (动态规划 + 三指针)

程序员文章站 2022-03-20 18:44:59
题目描述有些数的素因子只有 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倍)。举例说明...

题目描述

有些数的素因子只有 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;
.....

解题步骤

  1. 定义一个数组,该数组按照顺序存放整个过程中产生的素数(K个素数),由题意可知,第一个元素为1;
  2. 然后再定义三个指针p3,p5,p7:p3指向的数字永远乘3,p5指向的数字永远乘5,p7指向的数字永远乘7;
  3. 从dp[p3]*3 , dp[p5]*5 , dp[p7]*7 选取最小的一个数字,作为新的素数,并移动对应的指针;
  4. 重复执行上一步。
    这里基于的一个事实是,素数的数列是递增的,当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];
    }
};

复杂度分析:

  1. 时间复杂度:执行K次循环,因此时间复杂度为O(N);
  2. 空间复杂度:整个处理过程中会保存K个素数,因此空间复杂度为O(N)。

AC结果
LeetCode 刷题 [C++] [面试题 17.09]. 第 k 个数 (动态规划 + 三指针)

本文地址:https://blog.csdn.net/weixin_44953262/article/details/111026383