给定一个数int k，将素因子只有3、5、7的数从小到大排列，返回其中第k个数。保证k小于等于100。
测试样例：
3
返回：7
[编程题]第k个数
/*
* 时间复杂度O(N),按书中所讲，3个素数因子3、5、7分为三个队列
q3,q5,q7，其中最初存放3，5，7
* 之后每次添加找到三个队列头中最小的数，起初为3，将3移出队列
q3后，在q3添加3*3，在q5添加3*5,q7中添加3*7
* 此时可知q3{3*3},q5{5,3*5},q7{7,3*7}
* 下一轮找到最小数为5，重复上述步骤，将5从q5移出，添加5*5到
q5，因为5*3已经添加过所以不需要添加到q3中
* 将5*7添加到q7，结果q3{3*3},q5{3*5,5*5},q7{7,3*7,5*7}
* 依次找到第k个数
*/
public int findKth(int k) {
// write code here
if(k < 0){
return 0;
}
int val = 0;
Queue<Integer> q3 = new LinkedList<Integer>();
Queue<Integer> q5 = new LinkedList<Integer>();
Queue<Integer> q7 = new LinkedList<Integer>();
q3.add(1);
for(int i = 0 ; i <= k; i++){
int v3 = q3.size() > 0? q3.peek() : Integer.MAX_VALUE;
int v5 = q5.size() > 0? q5.peek() : Integer.MAX_VALUE;
int v7 = q7.size() > 0? q7.peek() : Integer.MAX_VALUE;
val = Math.min(v3, Math.min(v5,v7));
if(val == v3){
q3.remove();
q3.add(val*3);
q5.add(val*5);
}else if(val == v5){
q5.remove();
q5.add(val*5);
}else if(val == v7){
q7.remove();
}
q7.add(val*7);
}
return val;
}
编辑于 2015-11-02 14:27:13
回复(1)
import java.util.*;
/*
思路：每个数都是找三个数中最小的数*3或5或7得出来的，
*/
public class KthNumber {
public int findKth(int k) {
int [] array =new int[k];
int num3=0;
int num5=0;
int num7=0;
array[0]=3;
array[1]=5;
array[2]=7;
for(int i=3;i<k;i++){
array[i]=Math.min(Math.min(array[num3]*3,array[num5]*5),array[num7]*7);
if(array[i]==array[num3]*3) num3++;
if(array[i]==array[num5]*5) num5++;
if(array[i]==array[num7]*7) num7++;
}
return array[k-1];
}
}
运行时间：17ms
占用内存：8668k
发表于 2017-06-28 14:06:51
回复(6)
public int findKth(int k) {
// write code here
int[] map = new int[k + 1];
int mul3 = 0, mul5 = 0, mul7 = 0;
int result3 = 0, result5 = 0, result7 = 0;
int index = 1;
map[0] = 1;
while (index <= k) {
result3 = map[mul3] * 3;
result5 = map[mul5] * 5;
result7 = map[mul7] * 7;
if (result3 <= result5 && result3 <= result7) {
++mul3;
if (result3 > map[index - 1]) {
map[index] = result3;
++index;
}
} else if (result5 <= result3 && result5 <= result7) {
++mul5;
if (result5 > map[index - 1]) {
map[index] = result5;
++index;
}
} else if (result7 <= result3 && result7 <= result5) {
++mul7;
if (result7 > map[index - 1]) {
map[index] = result7;
++index;
}
}
}
return map[k];
}
发表于 2016-04-11 22:57:02
回复(0)
这道题的思路，首先可以排除偶数，因为2是素数，而且只能包含3，5，7素因子，可以这样理解，这样的数，最后一定会被拆成若干个3，若干个5，若干个7连成，不然不满足条件，所以代码如下
public static int findKth(int k) { // write code here int count=0; double i=3; while(count<k) { if(i%2!=0) { double b=i; while(b%3==0||b%5==0||b%7==0) { if(b%7==0) { b=b/7; } else if(b%5==0) { b=b/5; } else { b=b/3; } } if(b==1) { count++; } } i++; } return (int)i-1; }
发表于 2015-10-11 16:52:25
回复(2)
参考了wuafeing的思路：我来解释一下，如果一个数只有3，5，7这几个素因子，那一定是满足
这样形式的，3*5*7*k，所以首先除以3，然后除以5，最后除以7，如果是符合条件的，最后肯定
就是1，可能有人会说也可能是2，3，4，5，6啊，注意到这些数只有2，4可能，因为3，5在前面
已经作为除数了，最后的结果不会有3，5了，而6呢，本质就是2。
下面提供2种思路：
class KthNumber {
public:
int findKth(int k) {
/*int num = 3;
while(num && k){
int temp = num;
while(temp%3 ==0)
temp /= 3;
while(temp%5 ==0)
temp /= 5;
while(temp%7 ==0)
temp /= 7;
if(1 == temp)
k--;
num++;
}
return --num;*/
vector<int> res(k+1);
int i=0,j=0,t=0;
res[0]=1;
int num=0;
for(int h=1;h<=k;h++)//不能从0开始，不然res[0]=3;影响第二个数5的产生
{
num=min(res[i]*3,min(res[j]*5,res[t]*7));
res[h]=num;
if(num==res[i]*3) i++;
if(num==res[j]*5) j++;
if(num==res[t]*7) t++;
}
return res[k];
}
};
编辑于 2017-09-11 11:47:44
回复(0)
思路
- 使用三个队列q2、q3、q5，最初存放2、3、5；
- 取出队首最小的值： 2.1. 若从q2中取出，则分别X2、X3、X5，分别添加至q2、q3、q5的末尾； 2.2. 若从q3中取出，则分别X3、X5，分别添加至q3、q5的末尾； 2.3. 若从q5中取出，则分别X5，分别添加至q5的末尾；
代码
public int findKth(int k) {
LinkedList<Integer> q3 = new LinkedList<>();
LinkedList<Integer> q5 = new LinkedList<>();
LinkedList<Integer> q7 = new LinkedList<>();
q3.offer(3);
q5.offer(5);
q7.offer(7);
int index = 1;
int min = 0;
while( index<=k ){
min = Math.min(q3.peek(), Math.min(q5.peek(), q7.peek()));
if ( min==q3.peek() ) {
q3.poll();
q3.offer(min*3);
q5.offer(min*5);
q7.offer(min*7);
}
if ( min==q5.peek() ) {
q5.poll();
q5.offer(min*5);
q7.offer(min*7);
}
if ( min==q7.peek() ) {
q7.poll();
q7.offer(min*7);
}
index++;
}
return min;
}
发表于 2017-04-01 14:31:58
回复(0)
class KthNumber {
public:
int findKth(int k) {
// write code here
int num = 3;
while(num && k){
int temp = num;
while(temp%3 ==0)
temp /= 3;
while(temp%5 ==0)
temp /= 5;
while(temp%7 ==0)
temp /= 7;
if(1 == temp)
k--;
num++;
}
return --num;
}
};
//类似丑数算法！最简洁的，木有之一
发表于 2015-10-30 17:49:00
回复(2)
class KthNumber {
public:
int findKth(int k) {
// write code here
vector<int > num3,num5,num7;
int i3 = 0, i5 = 0, i7 = 0,res;
num3.push_back(3);
num5.push_back(5);
num7.push_back(7);
for (int i = 0; i < k; ++i) {
res = min(min(num3[i3],num5[i5]),num7[i7]);
if(res == num3[i3]) i3++;
if(res == num5[i5]) i5++;
if(res == num7[i7]) i7++;
num3.push_back(3 * res);
num5.push_back(5 * res);
num7.push_back(7 * res);
}
return res;
}
};
发表于 2019-06-11 14:52:50
回复(0)
class KthNumber {
public:
/* 关键：
1 下一个丑数 = 在之前生成的丑数数组中寻找一个数 * (3或5或7)，即大于当前丑数的最小值
设当前丑数为M
3*T3=M3 > M 【公式(1)】
5*T5=M5 > M 【公式(2)】
7*T7=M7 > M 【公式(3)】
从中令新的M = min(M3 , M5 , M7)，并更新T3,T5,T7，使得新的T3,有3*T3 > M，同理T5,T7 【操作1】
如果不更新，带来的问题就是，会陷入死循环
比如刚开始M=1,初始T3=T5=T7=1,满足上述条件后，M=3,此时3*T3 <= M,则T3=1没有等于3,同理后续T5=1,T7=1,而M=7,
之后就发现T3,T5,T7中没有一个能符合上述公式(1),(2),(3)，则M一直变成7不再变化；
为了防止这种情况，要进行上述操作1的处理，为的就是能够作为下一个丑数M的候选值能够一直变大
*/
int min(int a , int b , int c)
{
int minNum = a < b ? a : b;
minNum = minNum < c ? minNum : c;
return minNum;
}
int findKth(int k)
{
int *pArray = new int[k + 1];
pArray[0] = 1;
int* p3 , *p5 , *p7;
p3 = p5 = p7 = pArray;
int count = 0;
int minNum;
while(count < k)
{
count++;
minNum = min( *p3 * 3 , *p5 * 5 , *p7 * 7);
pArray[count] = minNum;
//注意等号不能取，while中循环条件如果改成 *p3 * 3 < minNum 是错误的，这样会陷入死循环，使得minNum候选的几个候选值不再变化
while( *p3 * 3 <= minNum )
{
p3++;
}
while( *p5 * 5 <= minNum)
{
p5++;
}
while( *p7 * 7 <= minNum)
{
p7++;
}
}
int result = pArray[k];
delete[] pArray;
return result;
}
};
public:
/* 关键：
1 下一个丑数 = 在之前生成的丑数数组中寻找一个数 * (3或5或7)，即大于当前丑数的最小值
设当前丑数为M
3*T3=M3 > M 【公式(1)】
5*T5=M5 > M 【公式(2)】
7*T7=M7 > M 【公式(3)】
从中令新的M = min(M3 , M5 , M7)，并更新T3,T5,T7，使得新的T3,有3*T3 > M，同理T5,T7 【操作1】
如果不更新，带来的问题就是，会陷入死循环
比如刚开始M=1,初始T3=T5=T7=1,满足上述条件后，M=3,此时3*T3 <= M,则T3=1没有等于3,同理后续T5=1,T7=1,而M=7,
之后就发现T3,T5,T7中没有一个能符合上述公式(1),(2),(3)，则M一直变成7不再变化；
为了防止这种情况，要进行上述操作1的处理，为的就是能够作为下一个丑数M的候选值能够一直变大
*/
int min(int a , int b , int c)
{
int minNum = a < b ? a : b;
minNum = minNum < c ? minNum : c;
return minNum;
}
int findKth(int k)
{
int *pArray = new int[k + 1];
pArray[0] = 1;
int* p3 , *p5 , *p7;
p3 = p5 = p7 = pArray;
int count = 0;
int minNum;
while(count < k)
{
count++;
minNum = min( *p3 * 3 , *p5 * 5 , *p7 * 7);
pArray[count] = minNum;
//注意等号不能取，while中循环条件如果改成 *p3 * 3 < minNum 是错误的，这样会陷入死循环，使得minNum候选的几个候选值不再变化
while( *p3 * 3 <= minNum )
{
p3++;
}
while( *p5 * 5 <= minNum)
{
p5++;
}
while( *p7 * 7 <= minNum)
{
p7++;
}
}
int result = pArray[k];
delete[] pArray;
return result;
}
};
发表于 2018-08-31 16:34:05
回复(0)
# -*- coding:utf-8 -*-
class KthNumber:
def findKth(self, k):
# write code here
queue3=[3]
queue5=[5]
queue7=[7]
count=0
while count<k:
min_s=min(queue3[0],queue5[0],queue7[0])
if min_s==queue3[0]:
min_s=queue3.pop(0)
queue3.append(min_s*3)
queue5.append(min_s*5)
elif min_s==queue5[0]:
min_s=queue5.pop(0)
queue5.append(min_s*5)
else:
min_s==queue7[0]
min_s=queue7.pop(0)
queue7.append(min_s*7)
count+=1
return min_s
编辑于 2017-07-11 11:18:37
回复(0)
//对于合法的数，存放于队列中，开始为：3,5,7
//以当前合法的数为基础，采用淘汰机制
//淘汰的原则是队列的首个元素如果乘以7小于队列最后一个元素
//则说明该元素乘以3,5,7均已经加入队列，该元素可以淘汰
//而队列添加元素的准则是当前元素乘以3,5,7中最小的一个
class KthNumber {
public:
int findKth(int k) {
vector<int> v{ 3, 5, 7 };
if (k <= 3) return v[k - 1];
int count = 3;
while (count < k){
if (v.front() * 7 <= v.back()) v.erase(v.begin());
else{
int i = 1, min = findMinAvaliable(v[0], v.back());
while (v[i] * 3 < min && i < v.size()){
if (findMinAvaliable(v[i], v.back()) < min){
min = findMinAvaliable(v[i], v.back());
}
i++;
}
v.push_back(min);
count++;
}
}
return *(v.end()-1);
}
int findMinAvaliable(int n, int key){
int min = 0;
if (n * 3 > key) min = n * 3;
else{
if (n * 5 > key) min = n * 5;
else min = n * 7;
}
return min;
}
};
发表于 2016-09-17 18:37:24
回复(0)
public int findKth(int k) {
// write code here
int[] nums = new int[k+1];
nums[0]=1;
int n3=0;
int n5=0;
int n7=0;
int index=0;
while(index<k){
index++;
nums[index] = min(nums[n3]*3,nums[n5]*5,nums[n7]*7);
if(nums[n3]*3==nums[index])
n3++;
if(nums[n5]*5==nums[index])
n5++;
if(nums[n7]*7==nums[index])
n7++;
}
return nums[index];
}
public int min(int a , int b,int c){
return Math.min(a,Math.min(b,c));
}
发表于 2016-08-27 23:42:32
回复(0)
//思路1：题目说保证K小于100，所以就用暴力法写一下了。
class KthNumber {
public:
int findKth(int k) {
// write code here
int count=0;
int i=3;
while(count<k)
{
if(isP(i))
{
count++;
}
i++;
}
return i-1;
}
bool isP(int number)
{
if(number<3) return false;
while(number%3==0) number=number/3;
while(number%5==0) number=number/5;
while(number%7==0) number=number/7;
return ((number==1)?true:false);
}
};
/*思路2:3,5,7满足题目要求，那么3,5,7的3倍、5倍、7倍依然是满足题目要求的；
用队列实现，代码如下。*/
class KthNumber {
public:
int findKth(int k) {
// write code here
queue<int> q3;
queue<int> q5;
queue<int> q7;
int count=1;
int i=1;
while(count<=k)
{
q3.push(i*3);
q5.push(i*5);
q7.push(i*7);
int min3=q3.front();
int min5=q5.front();
int min7=q7.front();
int min=((min3<min5)?min3:min5);
min=((min<min7)?min:min7);
if(min==min3) q3.pop();
if(min==min5) q5.pop();
if(min==min7) q7.pop();
i=min;
count++;
}
return i;
}
};
发表于 2016-08-12 09:40:07
回复(0)
十分朴素的解法，应该都能看懂。
class KthNumber {
public:
int findKth(int k) {
// write code here
if(k<=0)
return 0;
int temp;
int array[100]={0};
array[0]=3;array[1]=5;array[2]=7;
if(k<=3)
return array[k-1];
int t3,t5,t7,t31,t51,t71;
t31=t51=t71=0;
for(int i=3;i<100;i++){
t3 = 3 * array[t31];
t5 = 5 * array[t51];
t7 = 7 * array[t71];
if(t3<t5 && t3<t7){
array[i]=t3;
t31++;
}else{
if(t5<t7){
array[i]=t5;
t51++;
}else{
array[i]=t7;
t71++;
}
}
if(array[i]==array[i-1])
i--;
}
return array[k-1];
}
};
发表于 2016-05-20 01:35:19
回复(0)
public int findKth(int k) {
LinkedList<Integer> l1 = new LinkedList<>();
LinkedList<Integer> l2 = new LinkedList<>();
LinkedList<Integer> l3 = new LinkedList<>();
l1.add(3);
l2.add(5);
l3.add(7);
int val = 3;
for (int i = 1; i <= k; i++) {
int a = l1.peek(), b = l2.peek(), c = l3.peek();
val = Math.min(Math.min(a, b), c);
if (val == a) {
l1.removeFirst();
l1.add(val * 3);
l2.add(val * 5);
} else if (val == b) {
l2.removeFirst();
l2.add(val * 5);
} else
l3.removeFirst();
l3.add(val * 7);
}
return val;
}
发表于 2016-04-11 11:57:44
回复(0)
class KthNumber {
public:
int findKth(int k) {
if(k<0||k>100)
return 0;
int temp;
queue<int> q3,q5,q7;
q3.push(3);
q5.push(5);
q7.push(7);
for(int cn=0;cn<k;cn++)
{
temp=min(min(q3.front(),q5.front()),q7.front());
if(temp==q3.front())
{
q3.pop();
q3.push(temp*3);
q5.push(temp*5);
q7.push(temp*7);
}
else if(temp==q5.front())
{
q5.pop();
q5.push(temp*5);
q7.push(temp*7);
}
else
{
q7.pop();
q7.push(temp*7);
}
}
return temp;
}
};
我们可以用3个队列来维护这些数。第1个队列负责乘以3，第2个队列负责乘以5， 第3个队列负责乘以7。算法描述如下：
1. 初始化结果temp=1和队列q3,q5,q7
2. 分别往q3,q5,q7插入1*3,1*5,1*7
3. 求出三个队列的队头元素中最小的那个x，更新结果res=x
4. 如果x在：
q3中，那么从q3中移除x，并向q3，q5，q7插入3*x,5*x,7*x
q5中，那么从q5中移除x，并向q5，q7插入5*x,7*x
q7中，那么从q7中移除x，并向q7插入7*x
5. 重复步骤3－5，直到找到第k个满足条件的数
注意，当x出现在q5中，我们没往q3中插入3*x，那是因为这个数在q5中已经插入过了。
发表于 2015-10-10 16:49:30
回复(0)
class KthNumber {
public:
int findKth(int k) {
int num[105];
int pos3, pos5, pos7;
pos3 = pos5 = pos7 = 0;
num[0] = 1;
for(int i = 1 ; i <= k ; i++)
{
num[i] = min(num[pos3] * 3, min(num[pos5] * 5, num[pos7] * 7));
if(num[i] == num[pos3] * 3) pos3++;
if(num[i] == num[pos5] * 5) pos5++;
if(num[i] == num[pos7] * 7) pos7++;
}
return num[k];
}
};
发表于 2017-12-06 21:53:08
回复(0)
# -*- coding:utf-8 -*- class KthNumber: def findKth(self, k): # write code here result = [1] i3, i5, i7 = 0, 0, 0 while len(result) < k+1: result.append(min( 3 * result[i3], 5 * result[i5],7 * result[i7],)) if result[-1] == 3 * result[i3]: i3 += 1 if result[-1] == 5 * result[i5]: i5 += 1 if result[-1] == 7 * result[i7]: i7 += 1 return result[-1]
发表于 2020-10-20 20:15:03
回复(0)
问题信息
难度：
65条回答
75收藏
12250浏览
通过挑战的用户
查看代码-
2022-09-11 12:11:29 -
2022-08-20 21:00:46
-
2022-08-19 21:08:45
-
2022-07-29 14:27:34
-
2022-07-15 09:47:23
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
