「这是我参与11月更文挑战的第25天，活动详情查看：2021最后一次更文挑战」
有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 1，3，5，7，9，15，21。
示例 1:
输入: k = 5 输出: 9 复制代码
本题首先要解决的问题是如何求得更多的素因子只有 3，5，7的数
这里可以从 1 开始，用 1 去和 3，5，7 相乘得到 3，5，7，然后依次对后面的数重复该过程，就得到了更多的素因子只有 3，5，7 的数
将这个过程做到 7 得到的数组如下
[1,3,5,7,9,15,21,15,25,35,21,35]
可以看到这样的情况下我们虽然得到了符合题意要求的数字，但是里面会有重复的情况以及前大后小的情况
题解1
基于上述得到的条件，我们很自然的想到第一种解题思路：
- 将每一个值与 3，5，7 相乘得到更多的数字
- 将这些数组依次插入到一个数组中
- 插入之前需要判断数组中是否有该值，如果有，跳过
- 插入数组的时候，不是放到数组末尾，而是找到一个位置，前面的值都小于等于它，后面的值都大于它
- 这样找到符合条件的
k个数，第k个就是本题的结果
代码如下：
var getKthMagicNumber = function(k) { // 初始化数组 let arr = [1], // 标识当前处理数值的下标 cur = 0; // 当数组中数值数量小于 k*1.3 的时候，求得更多的符合条件的数字 // 不是k个是因为会出现前大后小的情况，所以第k个值出现的位置是在大于k的位置 while(arr.length<Math.floor(k*1.3)){ const num1 = arr[cur]*3, num2 = arr[cur]*5, num3 = arr[cur]*7; if(arr.indexOf(num1)===-1) arr = insert(arr,num1); if(arr.indexOf(num2)===-1) arr = insert(arr,num2); if(arr.indexOf(num3)===-1) arr = insert(arr,num3); cur++; } return arr[k-1] // 将num插入到合适的位置 function insert(arr,num){ let cur = arr.length-1; while(arr[cur]>num){ cur--; } arr.splice(cur+1,0,num); return arr; } } 复制代码
这里要注意的是，因为存在前大后小的情况，所以要找第 k 个值并不是如上处理过程中的第 k 个值，它的出现是要在第 k 个值之后的，这里我么有细致的去算到底要多出多少才会出现正确的第 k 个值，而是粗略的将数量增加了 30%
题解2
上述题解过程中，需要判断当前值是否出现过，而且插入过程中需要将新的数值插入到合适的位置，那么有没有办法直接求得当前位置正确的值呢？
这里我们可以使用如下方法
定义三个指针，分别代表当前 3，5，7每一个乘数要相乘的值在数组中的下标位置 初始化三个指针都指向 0,也就是数组中值为 1 的位置
然后用 3，5，7 分别乘以指针对应值，将三个数字中的最小值确定为当前位置的值
再将本次选定值对应的指针向后走一位
这样，就保证了每次获取的值是后续所有数值中的最小值，将其更新到当前位置，即为当前位置对应的正确的数值
代码如下：
var getKthMagicNumber = function(k) { // 初始化数组 const arr = [1]; // 初始化三个指针 let tail3 = tail5 = tail7 = 0; for(let i = 1;i<k;i++){ // 获取每个素因子与其指针对应值的乘积 const num1 = arr[tail3]*3, num2 = arr[tail5]*5, num3 = arr[tail7]*7; // 将最小值更新为当前位置的值 arr[i] = Math.min(num1,num2,num3); // 将对应指针的位置向后移动一位 if(arr[i]===num1) tail3++ if(arr[i]===num2) tail5++ if(arr[i]===num3) tail7++ } return arr[k-1] }; 复制代码
这里需要注意的是，因为会有重复的值，所以移动指针的时候，不可以使用 else if,而是都通过 if 判断处理
至此我们就完成了 leetcode-面试题17.09-第k个数
如有任何问题或建议，欢迎留言讨论！
