首页 > 试题广场 >

寻找丑数

[编程题]寻找丑数

热度指数：5007 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

输入描述:

整数N

输出描述:

第N个丑数

示例1

输入

输出

算法知识视频讲解

八歌

剑指offer上有这道题，感兴趣可以去看我之前写的https://blog.csdn.net/qq_34528297/article/details/72861876

public class Main {
    public static void main(String args[]){

        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            int n = scanner.nextInt();
            System.out.println(getTarget(n));
        }
    }

    public static int getTarget(int n){
        int[] arr = new int[n];
        arr[0] = 1;
        int t1 = 0;
        int t2 = 0;
        int t3 = 0;

        int nextNum = 1;
        while (nextNum < n){
            arr[nextNum] = Math.min((Math.min(arr[t1]*2,arr[t2]*3)),arr[t3]*5);
            if(arr[t1]*2 <= arr[nextNum])
                t1++;
            if(arr[t2]*3 <= arr[nextNum])
                t2++;
            if(arr[t3]*5 <= arr[nextNum])
                t3++;
            nextNum++;
        }

        return arr[n - 1];
    }
}

编辑于 2018-08-30 00:24:34 回复(0)

下雪不下雨

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=10010;
int main()
{
    int n;
    while(cin>>n)
    {
        int res[maxn]={0};
        res[0]=1;
        int index2=0,index3=0,index5=0;
        int i=0;
        while(i<n)
        {
            i+=1;
            
            res[i]=min(res[index2]*2,min(res[index3]*3,res[index5]*5));
            if(res[i]==res[index2]*2)
            {
                index2++;
            }
            if(res[i]==res[index3]*3)
            {
                index3++;
            }
            if(res[i]==res[index5]*5)
            {
                index5++;
            }
        }
        cout<<res[n-1]<<endl;
    }
}

发表于 2019-01-16 20:49:30 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int F(int n){
    int a[n+1];
    a[1] = 1;
    int i=1, j=1, k=1, cnt=2;
    while(cnt<=n){
        a[cnt] = min(min(2*a[i], 3*a[j]), 5*a[k]);
        if(a[cnt] == 2*a[i])
            i++;
        if(a[cnt] == 3*a[j])
            j++;
        if(a[cnt] == 5*a[k])
            k++;
        cnt++;
    }
    return a[n];
}

int main(){
    int n;
    scanf("%d", &n);
    printf("%d\n", F(n));
    return 0;
}

发表于 2020-11-04 00:36:34 回复(0)

kenecho

My solution:

def ugly_num(n, k=10000):
    ugly_array = [2, 3, 5]
    if n == 1:
        return 1
    else:
        latest_array = ugly_array
        while len(ugly_array) < k:
            new_array = []
            for i in latest_array:
                for j in [2, 3, 5]:
                    if i * j not in new_array:
                        new_array.append(i * j)
            ugly_array.extend(new_array)
            latest_array = new_array
    ugly_array = sorted(ugly_array)
    return ugly_array[n - 2]

发表于 2018-10-17 20:47:42 回复(0)

Douldon

import java.util.Scanner;
/*
 * 查找第n个丑数
 */
public class ted {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 题目要求查找的第n个丑数
        int n = sc.nextInt();
        // 已找到0个丑数
        int count = 0;
        // 从1开始查找
        int start = 1;
        // 当求得的丑数个数小于n；就不断start++，判断start是不是丑数。
        while (count < n) {
            int s = start;
            // 如果能被2/3/5整除，就一直除
            while ((s % 2) == 0 || s % 3 == 0 || s % 5 == 0) {
                if (s % 2 == 0) {
                    s = s / 2;
                } else if (s % 3 == 0) {
                    s = s / 3;
                } else if (s % 5 == 0) {
                    s = s / 5;
                }
            }
            // s==1，说明能被2/3/5除尽，说明是丑数。
            if (s == 1)
                count++;// 第count个丑数
            start++;
        }
        // 因为：循环末尾start++，用于下一轮计算，结果（start - 1）；
        System.out.println(start - 1);
        System.out.println("ok");
    }
}

编辑于 2018-08-27 17:30:26 回复(0)

Python

华科平凡

python一行解法

print(sorted([2**i*3**j*5**k  for i in range(30)  for j in range(20)   for k in range(15)])[int(input())-1] )

编辑于 2019-02-24 13:57:06 回复(5)

2222w

def ugly(n):
    res = [1]
    if n <=1 :
        return max(n,0)
    else:
        index2, index3, index5 = 0,0,0
        i = 0
        while i < n:
            i += 1
            res.append(min(res[index2]*2,res[index3]*3,res[index5]*5))
            if res[i] == res[index2]*2:
                index2 += 1
            if res[i] == res[index3]*3:
                index3 += 1
            if res[i] == res[index5]*5:
                index5 += 1
        return res[n-1]

用python写的

发表于 2018-08-24 15:56:12 回复(2)

wylu

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author wylu
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        System.out.println(getUglyNumber(n));
    }

    private static int getUglyNumber(int n) {
        if (n < 1) return 0;
        int[] arr = new int[n];
        arr[0] = 1;
        int t2 = 0, t3 = 0, t5 = 0;
        for (int i = 1; i < n; i++) {
            int m2 = arr[t2] * 2, m3 = arr[t3] * 3, m5 = arr[t5] * 5;
            arr[i] = Math.min(Math.min(m2, m3), m5);
            while (arr[t2] * 2 <= arr[i]) t2++;
            while (arr[t3] * 3 <= arr[i]) t3++;
            while (arr[t5] * 5 <= arr[i]) t5++;
        }
        return arr[n - 1];
    }
}

发表于 2019-01-24 21:33:28 回复(0)

请大佬带带我

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        // 已找到0个丑数
        int count = 0;
        // 从1开始查找
        int start = 1;
        // 当求得的丑数个数小于n；就不断start++，判断start是不是丑数。
        while (count < n) {
            int s = start;
            // 如果能被2、3、5整除，就一直除
            while (s % 2 == 0 || s % 3 == 0 || s % 5 == 0) {
                if (s % 2 == 0) {
                    s = s / 2;
                } else if (s % 3 == 0) {
                    s = s / 3;
                } else if (s % 5 == 0) {
                    s = s / 5;
                }
            }
            // s==1，说明能被2/3/5除尽，说明是丑数。
            if (s == 1) {
                // 第count个丑数
                count++;
            }
            start++;
        }
        System.out.println(start - 1);
    }
}

发表于 2021-12-28 11:35:31 回复(0)

C/C++

牛客549207409号

#include<iostream>
bool isun(int N)
{
while(N%2==0)
{
N/=2;
}
while(N%3==0)
{
N/=3;
}
while(N%5==0)
{
N/=5;
}
if(N==1)return true;
return false;
}
int main()
{
int N;
while(std::cin>>N)
{
int count=0;
int a=0;
while(count<N)
{
a++;
if(isun(a))count++;
}
std::cout<<a<<std::endl;
}
return 0;
}

发表于 2020-09-19 09:41:27 回复(0)

不啻逍遥然

n=int(input())
if n<1:
    print(0)
ans=[1]
p2,p3,p5=0,0,0
while len(ans)<n:
    a,b,c=ans[p2]*2,ans[p3]*3,ans[p5]*5
    temp=min(a,b,c)
    ans.append(temp)
    if a==temp:
        p2+=1
    if b==temp:
        p3+=1
    if c==temp:
        p5+=1
print(ans[-1])

发表于 2020-07-23 11:31:12 回复(0)

C/C++

哎哟喂怎么这么难起名字

#include<iostream>
#include<stdio.h>



using namespace std;
int main() {
	int N,i,t = 1;
	cin >> N;
	bool f = 1;
	for ( int j = 1; j <=N;)
	{
		i = t;
		f = 1;
		while (f)
		{
			f = 0;
			if (i % 2 == 0)
			{
				i /= 2;
				f = 1;
			}
			else if (i % 3 == 0)
			{
				i /= 3;
				f = 1;
			}
			else if (i % 5 == 0)
			{
				i /= 5;
				f = 1;
			}
			else
			{
				break;
			}
			if (i == 1)
			{
				break;

			}
		}
		if (i==1)
		{
			j++;
		}
		t++;
	
	}
	cout << t-1 << endl;
	
	system("pause");
	return 0;
}

发表于 2020-05-25 22:24:49 回复(0)

雄途~~~

<p>python </p>

发表于 2020-05-11 00:07:01 回复(0)

bingzibing

import java.util.*;
public class Main{
public static int findUglyNumber(int n){
if(n<=0){
return 0;//不满足条件的n直接返回0
}
ArrayList<Integer> result=new ArrayList<>();
result.add(1);
int i2=0;
int i3=0;
int i5=0;
while(result.size()<n){
int m2=result.get(i2)*2;
int m3=result.get(i3)*3;
int m5=result.get(i5)*5;
int min=Math.min(m2,Math.min(m3,m5));
result.add(min);
if(min==m2){
i2++;
}
if(min==m3){
i3++;
}
if(min==m5){
i5++;
}
}
return result.get(result.size()-1);
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int m=sc.nextInt();
System.out.println(findUglyNumber(m));
}
}

发表于 2020-02-15 13:02:04 回复(0)

阳光丿洒脱

#include<iostream>
#include<vector>
using namespace  std;

#include<algorithm>

int main()
{
    int N;
    while(cin>>N)
    {
        if(N<7)
            return N;
        
        vector<int>res(N);
        res[0]=1;
    
        int t2=0;
        int t3=0;
        int t5=0;
    
        for(int i=1;i<N;++i)
        {
            res[i]=min(res[t2]*2,min(res[t3]*3,res[t5]*5));
            if(res[i] == res[t2]*2)
                t2++;
            if(res[i] == res[t3]*3)
                t3++;
            if(res[i] == res[t5]*5)
                t5++;
        }
        printf("%d\n",res[N-1]);
    }
    return 0;
}

发表于 2020-01-03 14:28:16 回复(0)

·201909151023287

#include "stdafx.h"
#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int *p_nums = new int[n];
    int *p = p_nums;
    int i = 1;
    int m = n;
    while (n)
    {
        int num = i;
        while (i % 2 == 0)
            i = i / 2;
        while (i % 3 == 0)
            i = i / 3;
        while (i % 5 == 0)
            i = i / 5;
        if (i == 1)
        {
            *p_nums = num;
            n--;
            p_nums++;
        }
        i=num+1;
    }
    cout << p[m-1] << endl;
return 0;
}

发表于 2019-09-19 14:22:30 回复(0)

Java

飒飒的收到Z传说中

import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        System.out.print(GetUglyNumber(sc.nextInt()));
        sc.close();
    }
    
    public static int GetUglyNumber(int index) {
        if(index<=6)
            return index;
        int[] arr=new int[index];
        arr[0]=1;
        int t2=0,t3=0,t5=0;
        for(int i=1;i<index;i++){
           arr[i]=(Math.min(arr[t2]*2,Math.min(arr[t5]*5,arr[t3]*3)));
            if(arr[i]==arr[t2]*2) t2++;
            if(arr[i]==arr[t3]*3) t3++;
            if(arr[i]==arr[t5]*5) t5++;
        }
        return arr[index-1];
    }
}

发表于 2019-09-15 23:53:02 回复(0)

月亮上的熊猫

n = int(input())
a = [1]
N = 200000
for i in range(2,N):
    tmp = i
    while(tmp%5==0):
        tmp = tmp/5
    while(tmp%3==0):
        tmp = tmp/3
    while(tmp%2==0):
        tmp = tmp/2
    if tmp == 1:
        a.append(i)
print(a[n-1])

发表于 2019-08-25 20:56:57 回复(0)

C/C++

海问香12138

暴力枚举

#include <stdio.h>

int n,ans;

int choushu(int x);

int main()
{
	int i;
	scanf("%d",&n);
	for(i=1;ans<n;ans+=choushu(i++))	;
	printf("%d\n",i-1);
	return 0;
}

int choushu(int x)
{
	while(!(x%2))
		x >>= 1;
	while(!(x%3))
		x /= 3;
	while(!(x%5))
		x /= 5;
	return x==1;
}

发表于 2019-08-22 20:43:37 回复(0)

Farway

//想了半天想不明白，我这个代码为什么不对？？

#include<iostream>

usingnamespacestd;

booljudge(intnum)

{

if((num ==1)||(num ==2)||(num ==3)||(num==4)||(num ==5))

returntrue;

boolresult = 1;

intres = 1;

result = (num%2) &&(num%3)&&(num%5);

res = num%7;

if((result == 0)&&(res > 0))

returntrue; //是丑数

else

returnfalse;

}

intmain()

{

intnumber;

cin>>number;

intres;

intn = 1;

while(number)

{

boolchou = 0;

chou = judge(n);

if(chou)

number--;

n++;

}

cout<<n;

return0;

}

发表于 2019-05-31 11:51:08 回复(2)

提交观点

问题信息

C++工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师测试工程师 PHP工程师滴滴自动驾驶/地图融合查找系统工程师穷举数据挖掘工程师测试开发工程师 2018 数学 Java工程师

上传者：小小

难度：

27条回答 122收藏 10025浏览

通过挑战的用户

查看代码

牛客58917...

2022-11-15 13:46:59
牛客34242...

2022-10-15 11:33:19
阿小鱼

2022-10-15 10:30:49
牛客60961...

2022-10-15 09:57:03
牛客15066...

2022-10-14 21:26:10

寻找丑数

输入描述:

输出描述:

输入

输出

python一行解法

暴力枚举
#include <stdio.h> int n,ans; int choushu(int x); int main() { int i; scanf("%d",&n); for(i=1;ans<n;ans+=choushu(i++)) ; printf("%d\n",i-1); return 0; } int choushu(int x) { while(!(x%2)) x >>= 1; while(!(x%3)) x /= 3; while(!(x%5)) x /= 5; return x==1; }

问题信息

热门推荐

通过挑战的用户

相关试题

寻找丑数

输入描述:

输出描述:

输入

输出

python一行解法

暴力枚举 #include <stdio.h> int n,ans; int choushu(int x); int main() { int i; scanf("%d",&n); for(i=1;ans<n;ans+=choushu(i++)) ; printf("%d\n",i-1); return 0; } int choushu(int x) { while(!(x%2)) x >>= 1; while(!(x%3)) x /= 3; while(!(x%5)) x /= 5; return x==1; }

问题信息

热门推荐

通过挑战的用户

相关试题

暴力枚举
#include <stdio.h> int n,ans; int choushu(int x); int main() { int i; scanf("%d",&n); for(i=1;ans<n;ans+=choushu(i++)) ; printf("%d\n",i-1); return 0; } int choushu(int x) { while(!(x%2)) x >>= 1; while(!(x%3)) x /= 3; while(!(x%5)) x /= 5; return x==1; }