Ugly Number
出处
设计一个算法,找出只含素因子3,5,7 的第 k 大的数。
符合条件的数如:3,5,7,9,15......
样例
如果k=4, 返回 9
挑战
要求时间复杂度为O(nlogn)或者O(n)
Solution
DP method O(k)
假设数组ugly[N]中存放不断产生的丑数,初始只有一个丑数ugly[0]=1,由此出发,下一个丑数由因子2,3,5竞争产生,得到ugly[0]*2
, ugly[0]*3
, ugly[0]*5
, 显然最小的那个数是新的丑数,所以第2个丑数为ugly[1]=2,开始新一轮的竞争,由于上一轮竞争中,因子2获胜,这时因子2应该乘以ugly[1]才显得公平,得到ugly[1]*2
,ugly[0]*3
,ugly[0]*5
, 因子3获胜,ugly[2]=3,同理,下次竞争时因子3应该乘以ugly[1],即:ugly[1]*2
, ugly[1]*3
ugly[0]*5
, 因子5获胜,得到ugly[3]=5,重复这个过程,直到第n个丑数产生。总之:每次竞争中有一个(也可能是两个)因子胜出,下一次竞争中胜出的因子就应该加大惩罚!
注意这里不可以使用if/else 循环,因为有可能多于一个指针的结果是相等的:例如p3->5, p5->3, 他们的结果相等,这是两个指针都要+1
indexFor3 指的是上次乘完 3 之后需要加的惩罚。
Complexity
时间复杂度 O(n),空间复杂度 O(n)
Code
class Solution {
/**
* @param k: The number k.
* @return: The kth prime number as description.
*/
public long kthPrimeNumber(int k) {
long[] uglyNumbers = new long[k + 1];
int indexFor3 = 0, indexFor5 = 0, indexFor7 = 0; //multiplier index
uglyNumbers[0] = 1;
for (int i = 1; i <= k; i++) {
uglyNumbers[i] = Math.min(Math.min(3 * uglyNumbers[indexFor3], 5 * uglyNumbers[indexFor5]), 7 * uglyNumbers[indexFor7]);
if (uglyNumbers[i] == 3 * uglyNumbers[indexFor3]) {
indexFor3++;
}
if (uglyNumbers[i] == 5 * uglyNumbers[indexFor5]) {
indexFor5++;
}
if (uglyNumbers[i] == 7 * uglyNumbers[indexFor7]) {
indexFor7++;
}
}
return uglyNumbers[k];
}
};