第n个丑数

用户1148830

发布于 2018-01-03 10:06:23

89900

代码可运行

运行总次数：0

代码可运行

【题目描述】把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。【思路】首先想到的是肯定是暴力法，从1,2,3,…循环一直找到给定的第n个丑数，但是这种做法我记得在LeetCode是TLE的。那么有没有更elegant的方法呢？以下思路来自《剑指offer》第34题。既然一个个循环不可行，那么就生成第n个丑数呗。由于丑数只包含因子2,3,5，那么我们一个丑数只乘2,3,5的话也可以得到丑数。由于1是一个丑数，那么分别乘上2,3,5可以得2,3,5。显然，它们是丑数。但是注意4也是一个丑数，它可以由2 x 2得到。所以丑数可以再乘以2,3,5得到下一个丑数，唯一要保证的是应该从小到大得到下一个丑数。所以要分别保留2,3,5的上一个丑数指针，下一个丑数则是三个指针所指的数值分别乘以对应的因子中的最小值。

public class Solution {
    public int GetUglyNumber_Solution(int index) {
       if(index==0) return 0;//注意0的情况，没有加这一行牛客网上显示通过0%
       int count=1;
        int index_2=0,index_3=0,index_5=0;//三个因子的指针
        int number=1;
        int[] uglyNumber=new int[index];//用于保存前index个丑数
        uglyNumber[0]=1;
        while(count<index){
            int tmpnumber_2=uglyNumber[index_2]*2;
            int tmpnumber_3=uglyNumber[index_3]*3;
            int tmpnumber_5=uglyNumber[index_5]*5;
            number=Math.min(tmpnumber_2,Math.min(tmpnumber_3, tmpnumber_5));//最小的数作为下一个丑数
            uglyNumber[count]=number;
            while(uglyNumber[index_2]*2<=uglyNumber[count])
                index_2++;
            while(uglyNumber[index_3]*3<=uglyNumber[count])
                index_3++;
            while(uglyNumber[index_5]*5<=uglyNumber[count])
                index_5++;
            count++;
        }
        return number;
    }
}