第K个数

2021-03-21

题目描述

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

解题思路

由题设可知，起始的几个素数1、3、5、7，其中基础因子是3、5、7
后续的素数由3、5、7互相乘法结合(也就是因式分解后只有3、5、7这三个因子)
设num3、num5、num7代表3、5、7要取答案队列中第几个数来进行相乘(如3、5、7)就是与队列中第一位的1分别相乘的结果;9、15、21则是第二位3分别相乘的结果
后续数规律：3中各自在答案队列中取得的数乘以自身(3、5、7)，取三者最小的数为下一个入队的数，并且要将入答案队列的对应数加

举例说明

/*
1   
p3(1*3=3)最小-》下一位就是3->p3后移
p5(1*5=5)
p7(1*7=7)
----------
1   3
    p3(3*3=9)
p5(1*5=5)最小->下一位就是5-》p5后移
p7(1*7=7)
-----------
1   3   5
    p3(3*3=9)
    p5(3*5=15)
p7(1*7=7)最小->下一位就是7-》p7后移
----------
1   3   5   7
    p3(3*3=9)最小->下一位就是9-》p3后移
    p5(3*5=15)
    p7(3*7=21)
----------
...
但是有可能出现3*5=15, 5*3=15，数相等的情况,那么p3,和p5同时后移
*/

如何证明这个方法是成立的：(不重复，不遗漏)

对于不重复的证明是显然的，在推进过程中，每次循环结束后，加入数组中的值一定严格小于指针正在指向的值的倍率，因此数组是严格单调递增的 —— 3个if中，可能有两个是同时成立的，这导致了p3，p5，p7可能同时被推进一格。
对于不遗漏的严格证明，细节较为繁多，在此不做赘述。由于每个元素都是由数组内的元素的倍率生成的，我们可以通过考虑指针推进的过程，来直观得到这一结论。

const getKthMagicNumber = function (k) {
    let p3 = 0, p5 = 0, p7 = 0;
    let dp = new Array(k);
    dp[0] = 1;//第一个值为1
    for (let i = 0; i < k; i++) {
        //dp[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++;
        }
    }
    //返回第K个值
    return dp[k - 1];
}