当前位置: 首页 > news >正文

(剑指Offer)面试题34:丑数

题目:

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

思路:

1、逐个判断

逐个判断每个整数是不是丑数。根据丑数的定义,丑数只能被2,3,5整除,也就是说,如果一个数能被2整除,连续除以2,如果能被3整除,连续除以3,如果能被5整除,连续除以5,如果最后得到1,那么这个数就是丑数,否则就不是。

2、创建数组保存已经找到的丑数

第一种方法效率比较低,因为该方法对每个数无论是丑事还是非丑数,都进行了计算判断,这在一定程度上是浪费,有没有可能避免这种浪费呢?

根据丑数的定义,后面的丑数应该是前面丑数的2,3,5的倍数结果,因此我们可以创建一个数组,里面的数字是排好序的丑数,每一个丑数都是前面的丑数乘以2,3,5得到。

那么如何保证排序呢?假设当前数组中最大的丑数为M,我们把已有的每个丑数分别乘以2,3,5(实际上并不需要对每个丑数做乘积,只需每次保存上一次的位置即可),分别得到第一个乘以2后大于M的结果M2,第一个乘以3后大于M的结果M3,第一个乘以5后大于M的结果M5,那么下一个丑数就是M2,M3,M5的最小者。

代码:

1、逐个判断

bool isUgly(int n){
    while(n%2==0)
        n=n/2;
    while(n%3==0)
        n=n/3;
    while(n%4==0)
        n=n/5;
    if(n==1)
        return true;
    return false;
}

int getUglyNumber(int index){
    if(index<=0)
        return 0;
    int number=1;
    int count=0;
    while(count<=index){
        if(isUgly(number))
            count++;
        number++;
    }
    return number;
}

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
    	if(index<=0)
            return 0;
        int count=0;
        int number=0;
        while(count<index){
            ++number;
            if(isUgly(number))
                count++;
        }
        return number;
    }

    bool isUgly(int n){
        while(n%2==0)
            n=n/2;
        while(n%3==0)
            n=n/3;
        while(n/5==0)
            n=n/5;
        return (n==1)?true:false;
    }
};

2、只对丑数做操作

int min_3(int num1,int num2,int num3){
    num1=(num1<num2)?num1:num2;
    num1=(num1<num3)?num1:num3;
    return num1;
}

int getUglyNumber_1(int index){
    if(index<=0)
        return 0;
    int *uglyNumbers=new int[index];
    uglyNumbers[0]=1;
    int nextIndex=1;

    int *index_2=uglyNumbers;
    int *index_3=uglyNumbers;
    int *index_5=uglyNumbers;

    while(nextIndex<index){
        uglyNumbers[nextIndex]=min_3(*index_2*2,*index_3*3,*index_5*5);
        while(*index_2*2<=uglyNumbers[nextIndex]) ++index_2;
        while(*index_3*3<=uglyNumbers[nextIndex]) ++index_3;
        while(*index_5*5<=uglyNumbers[nextIndex]) ++index_5;
        ++nextIndex;
    }

    int ugly=uglyNumbers[index-1];
    delete[] uglyNumbers;
    return ugly;
}

在线测试OJ:

http://www.nowcoder.com/books/coding-interviews/6aa9e04fc3794f68acf8778237ba065b?rp=2

AC代码:

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
    	if(index<=0)
            return 0;
        int uglyNumbers[index];
        uglyNumbers[0]=1;
        int nextIndex=1;
        int index_2=0;
        int index_3=0;
        int index_5=0;
        
        while(nextIndex<index){
            uglyNumbers[nextIndex]=min_3(uglyNumbers[index_2]*2,uglyNumbers[index_3]*3,uglyNumbers[index_5]*5);
            while(uglyNumbers[index_2]*2<=uglyNumbers[nextIndex]) ++index_2;
            while(uglyNumbers[index_3]*3<=uglyNumbers[nextIndex]) ++index_3;
            while(uglyNumbers[index_5]*5<=uglyNumbers[nextIndex]) ++index_5;
            ++nextIndex;
        }
        return uglyNumbers[index-1];
    }
    
    int min_3(int num1,int num2,int num3){
    	num1=(num1<num2)?num1:num2;
    	num1=(num1<num3)?num1:num3;
    	return num1;
	}

};

  

相关文章:

  • HDU-5833 Zhu and 772002(异或方程高斯消元)
  • KMP + 求最小循环节 --- HDU 1358 Period
  • HDU-3605 Escape(状态压缩+最大流求多重匹配、改版匈牙利算法)
  • multiset的使用以及集合的运算
  • 为学IOS,进击中......
  • 2014-2015 ACM-ICPC, NEERC, Northern Subregional Contest I-Instruction(模拟)
  • jquery常用技巧及常用方法列表集合
  • Codeforces Round #439 (Div. 2) C.The Intriguing Obsession(组合数、记忆化搜索)
  • (第一天)包装对象、作用域、创建对象
  • UOJ-79 一般图的最大匹配(带花树模板求解)
  • POJ-2823 POJ-3250 (单调队列 单调栈)
  • 关于量价十八则的口诀
  • HDU-3478 Catch(二分图染色+并查集)
  • RSA密钥的生成与配置
  • POJ 2536 Gopher II
  • $translatePartialLoader加载失败及解决方式
  • CSS实用技巧
  • el-input获取焦点 input输入框为空时高亮 el-input值非法时
  • JAVA并发编程--1.基础概念
  • Linux快速配置 VIM 实现语法高亮 补全 缩进等功能
  • React-Native - 收藏集 - 掘金
  • Vue UI框架库开发介绍
  • webpack项目中使用grunt监听文件变动自动打包编译
  • windows下使用nginx调试简介
  • -- 查询加强-- 使用如何where子句进行筛选,% _ like的使用
  • 前端面试之闭包
  • 强力优化Rancher k8s中国区的使用体验
  • 深入浏览器事件循环的本质
  • 使用Envoy 作Sidecar Proxy的微服务模式-4.Prometheus的指标收集
  • 使用Maven插件构建SpringBoot项目,生成Docker镜像push到DockerHub上
  • 说说动画卡顿的解决方案
  • 微服务入门【系列视频课程】
  • 学习笔记TF060:图像语音结合,看图说话
  • 以太坊客户端Geth命令参数详解
  • 自动记录MySQL慢查询快照脚本
  • ​DB-Engines 11月数据库排名:PostgreSQL坐稳同期涨幅榜冠军宝座
  • #HarmonyOS:Web组件的使用
  • (30)数组元素和与数字和的绝对差
  • (ZT)薛涌:谈贫说富
  • (八)Docker网络跨主机通讯vxlan和vlan
  • (八)Flask之app.route装饰器函数的参数
  • (一)Linux+Windows下安装ffmpeg
  • (转载)VS2010/MFC编程入门之三十四(菜单:VS2010菜单资源详解)
  • **CI中自动类加载的用法总结
  • *p++,*(p++),*++p,(*p)++区别?
  • . ./ bash dash source 这五种执行shell脚本方式 区别
  • .NET Remoting学习笔记(三)信道
  • .NET WebClient 类下载部分文件会错误?可能是解压缩的锅
  • .net反混淆脱壳工具de4dot的使用
  • .net解析传过来的xml_DOM4J解析XML文件
  • .NET开发不可不知、不可不用的辅助类(三)(报表导出---终结版)
  • @Conditional注解详解
  • @Repository 注解
  • @test注解_Spring 自定义注解你了解过吗?
  • [ C++ ] STL_list 使用及其模拟实现