LeetCode :面试题 17.09. 第 k 个数 (三指针)

tech2023-08-21  107

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

 

最新回复(0)