有些数的素因子只有 3,5,7,请设计一个算法找出第 k 个数。注意,不是必须有这些素因子,而是必须不包含其他的素因子。例如,前几个数按顺序应该是 1,3,5,7,9,15,21。
示例 1:
输入: k = 5
输出: 9 通过次数5,384提交次数10,015
这道题呢,看懂了题目自然也是明白,就是从1开始乘3,5,7,然后排序,找到第K个数就ok,那么该怎么才能找到呢
这里用三指针
第一个指针是指向*3 第二个*5,第三个*7
每次选取最小的数,让指针往后++;
class Solution { public int getKthMagicNumber(int k) { int [] numList=new int[k+1]; int p3=0,p5=0,p7=0; numList[0]=1; for(int 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]; } }