The eligible numbers are like 3, 5, 7, 9, 15 ...
Example
If k=4, return 9.
/*
class Solution {
public:
long long kthPrimeNumber(int k) {
vector<long long> h(k+1, 0);
h[0] = 1;
int i3 = 0, i5 = 0, i7 = 0;
for(int i = 1; i <= k; i++) {
long long x3 = 3 * h[i3], x5 = 5*h[i5], x7 = 7 * h[i7];
h[i] = min(x3, min(x5, x7));
if (x3 == h[i]) i3++;
if (x5 == h[i]) i5++;
if (x7 == h[i]) i7++;
}
return h[k];
}
};
class Solution {
public:
long long kthPrimeNumber(int k) {
queue<long long> q3, q5, q7;
q3.push(3); q5.push(5); q7.push(7);
long long result;
for(int i = 0; i < k; i++) {
long long t3 = q3.size() > 0? q3.front() : LONG_MAX;
long long t5 = q5.size() > 0? q5.front() : LONG_MAX;
long long t7 = q7.size() > 0? q7.front() : LONG_MAX;
result = min(t3, min(t5, t7));
if (result == t3) {
q3.pop();
q3.push(result*3);
q5.push(result*5);
}
if (result == t5){
q5.pop();
q5.push(result*5);
}
if (result == t7)
q7.pop();
q7.push(result*7);
}
return result;
}
};
*/
class Solution {
public:
long long kthPrimeNumber(int k) {
vector<long long> h(k+1, 0);
h[0] = 1;
int i3 = 0, i5 = 0, i7 = 0;
for(int i = 1; i <= k; i++) {
long long x3 = 3 * h[i3], x5 = 5*h[i5], x7 = 7 * h[i7];
h[i] = min(x3, min(x5, x7));
while(h[i3]*3 <= h[i]) i3++;
while(h[i5]*5 <= h[i]) i5++;
while(h[i7]*7 <= h[i]) i7++;
}
return h[k];
}
};
No comments:
Post a Comment