剑指Offer（三十三）丑数（Java版 )

刺骨的言语ヽ痛彻心扉 2021-09-26 23:36 182阅读 0赞

# 一、题目描述 #

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

# 二、题目分析 #

方法一：  
最简单的方法就是先通过将一个数不断除以2，3，5来判定该数是不是丑数，而后在从1开始，依次往后判断每个数是不是丑数，并记下丑数的个数，这样当计算的个数为给定值时，便是需要求的第n个丑数，这种方法的时间复杂度为O（k），这里的k为第n个丑数的大小，比如第1500个丑数的大小为859963392，那么就需要判断859963392次，时间效率非常低。

public class Solution {
        //判断是否是丑数
        public boolean ChouShuMa(int number)
        {
            while(number % 2 == 0)
                number /= 2;
            while(number % 3 == 0)
                number /= 3;
            while(number % 5 == 0)
                number /= 5;
            //如果是丑数，就返回true
            return (number == 1) ? true : false;
        }
        public int GetUglyNumber_Solution(int index) {
            if(index <= 0)
            return 0;
            int number = 0;
            int ChouShuGeShu = 0;
            //如果丑数个数小于Index,那就一直循环就行找
            while(ChouShuGeShu < index)
            {
                ++number;
                if(ChouShuMa(number))
                {
                    ++ChouShuGeShu;
                }
            }
            //将这个数返回
            return number;
        }
    }

运行结果：  
![这里写图片描述][70]  
方法二：  
直观的优化措施就是看能不能将时间复杂度降低到O（n），即只在丑数上花时间，而不在非丑数上浪费时间。用O（n）的辅助空间来得到O(n)的时间复杂度。其核心思想是：每一个丑数必然是由之前的某个丑数与2，3或5的乘积得到的，这样下一个丑数就用之前的丑数分别乘以2，3，5，找出这三这种最小的并且大于当前最大丑数的值，即为下一个要求的丑数。

import java.util.*;
    public class Solution
    {
        public int GetUglyNumber_Solution(int n)
        {
            if(n == 0) return 0;
            ArrayList<Integer> array=new ArrayList<Integer>();
            //因为1是丑数，先将1添加进来
            array.add(1);
            int i2 = 0,i3 = 0,i5 = 0;
            while(array.size() < n)
            {
                int m2 = array.get(i2)*2;
                int m3 = array.get(i3)*3;
                int m5 = array.get(i5)*5;
                //将三个数中的最小值添加进来
                int min = Math.min(m2 , Math.min( m3 , m5 ) );
                array.add(min);
                if(min == m2)i2++;
                if(min == m3)i3++;
                if(min == m5)i5++;
            }
            return array.get( array.size() - 1 );
        }
    }

运行结果：  
![这里写图片描述][70 1]

[70]: /images/20210923/7551f3e149a44e4fb85faf4fd955be66.png
[70 1]: /images/20210923/3c467fd3ddb849cfafad56a554784eb9.png