第K个数 牛客网 程序员面试金典 C++ Python
题目描述
有一些数的素因子只有3、5、7，请设计一个算法，找出其中的第k个数。
给定一个数int k，请返回第k个数。保证k小于等于100。
测试样例：
3
返回：7
C++
class KthNumber { public: //run:3ms memory:504k int findKth(int k){ vector<int> res(k+1,0); res[0] = 1; int t3 = 0; int t5 = 0; int t7 = 0; for(int i = 1; i <= k; i++){ res[i] = min(res[t3] * 3, min(res[t5] * 5,res[t7]*7)); if(res[i] == res[t3] * 3) t3++; if(res[i] == res[t5] * 5) t5++; if(res[i] == res[t7] * 7) t7++; } return res[k]; } };Python
class KthNumber: def findKth(self, k): ret = [] ret.append(1) t3 = 0 t5 = 0 t7 = 0 for i in range(1,k+1): v = min(ret[t3]*3,min(ret[t5]*5,ret[t7]*7)) ret.append(v) if ret[i] == ret[t3]*3: t3 += 1 if ret[i] == ret[t5]*5: t5 += 1 if ret[i] == ret[t7]*7: t7 += 1 return ret[k]
转载于:https://www.cnblogs.com/vercont/p/10210305.html
