首页 > 试题广场 >

寻找丑数

[编程题]寻找丑数
  • 热度指数：4893 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

输入描述:
整数N


输出描述:
第N个丑数
示例1

输入

6

输出

6
算法知识视频讲解
添加回答
2222w头像 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)
八歌头像 八歌

剑指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头像 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头像 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头像 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)
wylu头像 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号头像 牛客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头像 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头像 ·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传说中头像 飒飒的收到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头像 海问香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头像 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条回答 7703浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号