程序员面试金典

程序员面试金典--第k个数

题目描述

有一些数的素因子只有3、5、7，请设计一个算法，找出其中的第k个数。

给定一个数int k，请返回第k个数。保证k小于等于100。

测试样例：

3

返回：7

 

逐个增加，直到找到第k个数。

 

class KthNumber {
public:
    int findKth(int k) {
        // write code here
        vector<int> vt{3, 5, 7}; 
        int pt3 = 0, pt5 = 0, pt7 = 0; 
        for(int i=4; i<=k; ++i){
            int val = min(3*vt[pt3], min(5*vt[pt5], 7*vt[pt7])); 
            if(val == 3*vt[pt3]){ pt3++; } 
            if(val == 5*vt[pt5]){ pt5++; } 
            if(val == 7*vt[pt7]){ pt7++; } 
            vt.push_back(val); 
        }
        return vt[k-1]; 
    }
};