面试题 17.09. 第 k 个数（技巧）

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

---

示例 1:

输入: k = 5

输出: 9

---

【思路】：
此题类似丑数那一题：

不难发现，一个丑数总是由前面的某一个丑数 x3 / x5 / x7 得到。
反过来说也是一样的，一个丑数 x3 / x5 / x7 就会得到某一个更大的丑数。

如果把丑数数列叫做 ugly[i]，那么考虑一下三个数列：

1. ugly[0]*3,ugly[1]*3,ugly[2]*3,ugly[3]*3,ugly[4]*3,ugly[5]*3……
2. ugly[0]*5,ugly[1]*5,ugly[2]*5,ugly[3]*5,ugly[4]*5,ugly[5]*5……
3. ugly[0]*7,ugly[1]*7,ugly[2]*7,ugly[3]*7,ugly[4]*7,ugly[5]*7……

上面这个三个数列合在一起就形成了新的、更长的丑数数列。

如果合在一起呢？这其实就是一个合并有序线性表的问题。

定义三个index 分别指向上面三个数列，下一个丑数一定是三个 index 代表的值中最小的那个。然后相应 index++ 即可。

作者：orangex
链接：https://leetcode.cn/problems/get-kth-magic-number-lcci/solution/di-k-ge-shu-jiu-shi-xiang-bu-tong-wei-he-san-zhi-z/
来源：力扣（LeetCode）

---

所以其实转化成一个合并有序链表的题。和归并排序中的并是一样，只不过这里是合并三个链表。

---

【代码】：

/**
 * @param {number} k
 * @return {number}
 */
var getKthMagicNumber = function(k) {
    var numList = new Array(k + 1).fill(0)
    numList[0] = 1;
    var p3=0,p5=0,p7=0;
    for(let i = 1;i < k;i++){
        numList[i]=Math.min(Math.min(numList[p3]*3,numList[p5]*5),numList[p7]*7);
        if(numList[i]==numList[p3]*3) p3++;
        if(numList[i]==numList[p5]*5) p5++;
        if(numList[i]==numList[p7]*7) p7++;
    }
    return numList[k-1]; 
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16