首页 > 试题广场 > 丑数
[编程题]丑数
把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
推荐
class Solution {
public://别人的代码就是精简,惭愧啊,继续学习。
    int GetUglyNumber_Solution(int index) {
		if (index < 7)return index;
		vector<int> res(index);
		res[0] = 1;
		int t2 = 0, t3 = 0, t5 = 0, i;
		for (i = 1; i < index; ++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++;
		}
		return res[index - 1];
    }
};

编辑于 2019-01-10 19:24:15 回复(121)
通俗易懂的解释:
首先从丑数的定义我们知道,一个丑数的因子只有2,3,5,那么丑数p = 2 ^ x * 3 ^ y * 5 ^ z,换句话说一个丑数一定由另一个丑数乘以2或者乘以3或者乘以5得到,那么我们从1开始乘以2,3,5,就得到2,3,5三个丑数,在从这三个丑数出发乘以2,3,5就得到4,6,10,6,9,15,10,15,25九个丑数,我们发现这种方法会得到重复的丑数,而且我们题目要求第N个丑数,这样的方法得到的丑数也是无序的。那么我们可以维护三个队列:
(1)丑数数组: 1
乘以2的队列:2
乘以3的队列:3
乘以5的队列:5
选择三个队列头最小的数2加入丑数数组,同时将该最小的数乘以2,3,5放入三个队列;
(2)丑数数组:1,2
乘以2的队列:4
乘以3的队列:3,6
乘以5的队列:5,10
选择三个队列头最小的数3加入丑数数组,同时将该最小的数乘以2,3,5放入三个队列;
(3)丑数数组:1,2,3
乘以2的队列:4,6
乘以3的队列:6,9
乘以5的队列:5,10,15
选择三个队列头里最小的数4加入丑数数组,同时将该最小的数乘以2,3,5放入三个队列;
(4)丑数数组:1,2,3,4
乘以2的队列:6,8
乘以3的队列:6,9,12
乘以5的队列:5,10,15,20
选择三个队列头里最小的数5加入丑数数组,同时将该最小的数乘以2,3,5放入三个队列;
(5)丑数数组:1,2,3,4,5
乘以2的队列:6,8,10,
乘以3的队列:6,9,12,15
乘以5的队列:10,15,20,25
选择三个队列头里最小的数6加入丑数数组,但我们发现,有两个队列头都为6,所以我们弹出两个队列头,同时将12,18,30放入三个队列;
……………………
疑问:
1.为什么分三个队列?
丑数数组里的数一定是有序的,因为我们是从丑数数组里的数乘以2,3,5选出的最小数,一定比以前未乘以2,3,5大,同时对于三个队列内部,按先后顺序乘以2,3,5分别放入,所以同一个队列内部也是有序的;
2.为什么比较三个队列头部最小的数放入丑数数组?
因为三个队列是有序的,所以取出三个头中最小的,等同于找到了三个队列所有数中最小的。
实现思路:
我们没有必要维护三个队列,只需要记录三个指针显示到达哪一步;“|”表示指针,arr表示丑数数组;
(1)1
|2
|3
|5
目前指针指向0,0,0,队列头arr[0] * 2 = 2,  arr[0] * 3 = 3,  arr[0] * 5 = 5
(2)1 2
2 |4
|3 6
|5 10
目前指针指向1,0,0,队列头arr[1] * 2 = 4,  arr[0] * 3 = 3, arr[0] * 5 = 5
(3)1 2 3
2| 4 6
3 |6 9
|5 10 15
目前指针指向1,1,0,队列头arr[1] * 2 = 4,  arr[1] * 3 = 6, arr[0] * 5 = 5
………………
class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        // 0-6的丑数分别为0-6
        if(index < 7) return index;
        //p2,p3,p5分别为三个队列的指针,newNum为从队列头选出来的最小数
        int p2 = 0, p3 = 0, p5 = 0, newNum = 1;
        vector<int> arr;
        arr.push_back(newNum);
        while(arr.size() < index) {
            //选出三个队列头最小的数
            newNum = min(arr[p2] * 2, min(arr[p3] * 3, arr[p5] * 5));
            //这三个if有可能进入一个或者多个,进入多个是三个队列头最小的数有多个的情况
            if(arr[p2] * 2 == newNum) p2++;
            if(arr[p3] * 3 == newNum) p3++;
            if(arr[p5] * 5 == newNum) p5++;
            arr.push_back(newNum);
        }
        return newNum;
    }
};

编辑于 2018-04-19 14:57:54 回复(45)
/*
说下思路,如果p是丑数,那么p=2^x * 3^y * 5^z
那么只要赋予x,y,z不同的值就能得到不同的丑数。
如果要顺序找出丑数,要知道下面几个特(fei)点(hua)。
对于任何丑数p:
(一)那么2*p,3*p,5*p都是丑数,并且2*p<3*p<5*p
(二)如果p<q, 那么2*p<2*q,3*p<3*q,5*p<5*q
现在说说算法思想:
    由于1是最小的丑数,那么从1开始,把2*1,3*1,5*1,进行比较,得出最小的就是1
的下一个丑数,也就是2*1,
    这个时候,多了一个丑数‘2’,也就又多了3个可以比较的丑数,2*2,3*2,5*2,
这个时候就把之前‘1’生成的丑数和‘2’生成的丑数加进来也就是
(3*1,5*1,2*2,3*2,5*2)进行比较,找出最小的。。。。如此循环下去就会发现,
每次选进来一个丑数,该丑数又会生成3个新的丑数进行比较。
    上面的暴力方法也应该能解决,但是如果在面试官用这种方法,估计面试官只会摇头吧
。下面说一个O(n)的算法。
    在上面的特(fei)点(hua)中,既然有p<q, 那么2*p<2*q,那么
“我”在前面比你小的数都没被选上,你后面生成新的丑数一定比“我”大吧,那么你乘2
生成的丑数一定比我乘2的大吧,那么在我选上之后你才有机会选上。
其实每次我们只用比较3个数:用于乘2的最小的数、用于乘3的最小的数,用于乘5的最小的
数。也就是比较(2*x , 3*y, 5*z) ,x>=y>=z的,
重点说说下面代码中p的作用:int p[] = new int[] { 0, 0, 0 }; p[0]表示最小用于
乘2比较数在数组a中的【位置】。 */
public class Solution {
  	final int d[] = { 2, 3, 5 };
	public int GetUglyNumber_Solution(int index) {
        if(index == 0) return 0;
		int a[] = new int[index];
		a[0] = 1;
		int p[] = new int[] { 0, 0, 0 };
        int num[] = new int[] { 2, 3, 5 };
		int cur = 1;

		while (cur < index) {
			int m = finMin(num[0], num[1], num[2]);
			if (a[cur - 1] < num[m]) 
				a[cur++] = num[m];
			p[m] += 1;
			num[m] = a[p[m]] * d[m];
		}
		return a[index - 1];
	}

	private int finMin(int num2, int num3, int num5) {
		int min = Math.min(num2, Math.min(num3, num5));
		return min == num2 ? 0 : min == num3 ? 1 : 2;
	}
}

编辑于 2016-05-09 15:42:50 回复(33)
public int GetUglyNumber_Solution2(int n)
    {
        if(n<=0)return 0;
        ArrayList<Integer> list=new ArrayList<Integer>();
        list.add(1);
        int i2=0,i3=0,i5=0;
        while(list.size()<n)//循环的条件
        {
            int m2=list.get(i2)*2;
            int m3=list.get(i3)*3;
            int m5=list.get(i5)*5;
            int min=Math.min(m2,Math.min(m3,m5));
            list.add(min);
            if(min==m2)i2++;
            if(min==m3)i3++;
            if(min==m5)i5++;
        }
        return list.get(list.size()-1);
    }
该思路: 我们只用比较3个数:用于乘2的最小的数、用于乘3的最小的数,用于乘5的最小的

发表于 2016-07-05 11:06:18 回复(29)
//要注意,后面的丑数是有前一个丑数乘以2,3,5中的一个得来。因此可以用动态规划去解
//同时注意一下,题目意思应该是质数因此,而不是因子,因为8的因子有1,2,4,8
class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if (index<=0) return 0;
        if (index==1) return 1;
        vector<int>k(index);k[0]=1;
        int t2=0,t3=0,t5=0;
        for (int i=1;i<index;i++) {
            k[i]=min(k[t2]*2,min(k[t3]*3,k[t5]*5));
            if (k[i]==k[t2]*2) t2++;
            if (k[i]==k[t3]*3) t3++;
            if (k[i]==k[t5]*5) t5++;
        }
        return k[index-1];
    }
};

编辑于 2016-09-15 18:31:14 回复(32)
《参考程序员面试金典》伪代码如下
1)初始化array和队列:Q2 Q3 Q5
2)将1插入array
3)分别将1*2、1*3 、1*5插入Q2 Q3 Q5
4)令x为Q2 Q3 Q5中的最小值,将x添加至array尾部
5)若x存在于:
    Q2:将 x * 2、x * 3、x*5 分别放入Q2 Q3 Q5,从Q2中移除x
    Q3:将 x * 3、x*5 分别放入Q3 Q5,从Q3中移除x
    Q5:将 x * 5放入Q5,从Q5中移除x
6)重复步骤4~6,知道找到第k个元素
int GetUglyNumber_Solution(int index) {
	if (index < 1)
		return NULL;

	int minVal = 0;
	queue<int> q2, q3, q5;
	q2.push(1);

	for (int i = 0; i < index; i++)
	{
		int val2 = q2.empty() ? INT_MAX : q2.front();
		int val3 = q3.empty() ? INT_MAX : q3.front();
		int val5 = q5.empty() ? INT_MAX : q5.front();

		minVal = min(val2, min(val3, val5));

		if (minVal == val2)
		{
			q2.pop();
			q2.push(2 * minVal);
			q3.push(3 * minVal);
		}
		else if (minVal == val3)
		{
			q3.pop();
			q3.push(3 * minVal);
		}
		else
		{
			q5.pop();
		}

		q5.push(5 * minVal);
	}

	return minVal;
}

编辑于 2015-09-10 00:26:00 回复(11)
public int GetUglyNumber_Solution(int index) {
        if(index<7) return index;
        int[] ret = new int[index];
        ret[0]=1;
        int t2=0,t3=0,t5=0;
        for(int i=1;i<index;i++) {
            ret[i] = min(min(ret[t2]*2,ret[t3]*3),ret[t5]*5);
            if(ret[i] == ret[t2]*2) t2++;
            if(ret[i] == ret[t3]*3) t3++;
            if(ret[i] == ret[t5]*5) t5++;
        }
        return ret[index-1];
    }
    public static int min(int a,int b) {
        return a<b ? a : b; 
    }
所有的丑数分为三种类型 2*i,3*i,5*i     其中 i是数组中的元素,一开始只有1
2*1  3*1  5*1
2*2  3*1  5*1
2*2  3*2  5*1
2*3  3*2  5*1
2*3  3*2  5*2
2*4  3*3  5*2
2*5  3*3  5*2
2*5  3*4  5*2
2*6  3*4  5*3
2*8  3*5  5*3
2*8  3*6  5*4
发表于 2018-03-04 13:04:19 回复(10)
思路:按顺序把每个丑数放在数组中,求下一个丑数
下一个丑数必定由有数组中的某一个丑数A * 2, B * 3, C * 5 的中的最小值得来。
分析:在数组中必定有一个丑数M2, 在它之前的数 * 2 都小于当前最大丑数, 在它之后的数 * 2都大于当前最大丑数, 同样有M3, M5

# -*- coding:utf-8 -*-
class Solution:
    def GetUglyNumber_Solution(self, index):
        if index < 1:
            return 0

        res = [1]
        t2 = t3 = t5 = 0

        nextIdx = 1
        while nextIdx < index:
            minNum = min(res[t2] * 2, res[t3] * 3, res[t5] * 5)
            res.append(minNum)

            while res[t2] * 2 <= minNum:
                t2 += 1
            while res[t3] * 3 <= minNum:
                t3 += 1
            while res[t5] * 5 <= minNum:
                t5 += 1

            nextIdx += 1

        return res[nextIdx - 1] 


发表于 2016-07-26 17:56:26 回复(6)

python 三行解法:

def GetUglyNumber_Solution(self, index):
        res=[2**i*3**j*5**k  for i in range(30)  for j in range(20)   for k in range(15)]
        res.sort()
        return res[index-1] if index else 0

两行解法

    def GetUglyNumber_Solution(self, index):
        res=[2**i*3**j*5**k  for i in range(30)  for j in range(20)   for k in range(15)]
        return sorted(res)[index-1] if index else 0

更装逼的一行解法。

return sorted([2**i*3**j*5**k  for i in range(30)  for j in range(20)   for k in range(15)])[index-1] if index else 0
编辑于 2017-10-14 14:15:12 回复(28)
import java.util.*;

public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if(index<=0)
        	return 0;
        ArrayList<Integer> list = new ArrayList<Integer>();
        //add进第一个丑数1
        list.add(1);
        //三个下标用于记录丑数的位置
        int i2=0,i3=0,i5=0;
        while(list.size()<index){
            //三个数都是可能的丑数,取最小的放进丑数数组里面
            int n2=list.get(i2)*2;
            int n3=list.get(i3)*3;
            int n5=list.get(i5)*5;
            int min = Math.min(n2,Math.min(n3,n5));
            list.add(min);
            if(min==n2)
                i2++;
            if(min==n3)
                i3++;
            if(min==n5)
                i5++;
        }
        return list.get(list.size()-1);
    }
}

发表于 2017-08-24 04:47:29 回复(6)
  思路一:逐个判断每个整数是不是丑数的解法,直观但不高效(牛客网测试超时)
       所谓一个数m是另一个数n的因子,是指n能被m整数,也就是n%m==0。根据丑数的定义,丑数只能被2、3和5整数。也就是说如果一个数能被2整除,我们就把它连续除以2;如果能被3整数,就连续除以3;如果能被5整除,就除以连续5。如果最后我们得到的数字是1,那么这个数就是丑数,否则不是。该算法非常直观,代码也非常简洁,但 最大的问题是每个整数都需要计算。即使一个数字不是丑数,我们还是需要对它做求余和除法操作 。因此该算法的时间效率不够高,面试官也不会就此满足。
       思路二:创建数组保存已找到的丑数,用空间换时间的解法
       前面的算法之所以效率低,很大程度上是因为不管一个数是不是丑数,我们对它都要作计算。接下来我们试着找到一种只要计算丑数的方法,而不在非丑数的整数上浪费时间。根据丑数的定义, 丑数应该是另一个丑数乘以2、3或者5的结果(1除外) 。因此我们可以创建一个数组,里面的数字是排好序的丑数,每一个丑数都是前面的丑数乘以2、3或者5得到的。
       这种思路的关键在于怎样确保数组里面的丑数是排好序的。假设数组中已经有若干个丑数排好序后放在数组中,并且把 已有最大的丑数记做M ,我们接下来分析如何生成下一个丑数。该丑数肯定是前面某一个丑数乘以2、3或者5的结果,所以我们首先考虑把已有的每个丑数乘以2。在乘以2的时候,可以得到多干个小于等于M的结果。由于是按顺序生成的,小于或者等于M肯定已经在数组中了,我们不需要再考虑;还会得到若干个大于M的结果,但我们只需要第一个大于M的结果,因为我们希望丑数是按照从小到大的顺序生成的,其他更大的结果以后再说。我们把得到的第一个乘以2后大于M的丑数记为M2。同样,我们把已有的每一个丑数乘以3和5,能得到第一个大于M的结果M3和M5。那么下一个丑数应该是M2、M3和M5这三个数的最小者了
        前面分析的时候,提到把已有的丑数分别乘以2、3和5。事实上这不是必须的,因为已有的丑数是按照顺序放在数组中的。对乘以2而言,肯定存在某一个丑数T2,排在它之前的每一个乘以2得到的结果都会小于已有最大的丑数,在它之后的每一个丑数乘以2得到的结果都会太大。我们只需要记下这个丑数的位置,同时每次生成新的丑数的时候,取更新这个这个T2.对于乘以3和5而言,也存在着同样的T3和T5。     
class Solution {
public:
    int GetUglyNumber_Solution(int index) {
       if(index<=0)
           return 0;
    int *pUglyNumber=new int[index];
    pUglyNumber[0]=1;
    int NextUglyIndex=1;
    int *pMutiply2=pUglyNumber;
    int *pMutiply3=pUglyNumber;
    int *pMutiply5=pUglyNumber;
    
    while(NextUglyIndex<index)
        {
           int min=Min(*pMutiply2*2,*pMutiply3*3,*pMutiply5*5);
           pUglyNumber[NextUglyIndex]=min;
           while(*pMutiply2*2<=pUglyNumber[NextUglyIndex])   //当前最大丑数pUglyNumber[NextUglyIndex]
               pMutiply2++;
           while(*pMutiply3*3<=pUglyNumber[NextUglyIndex])
               pMutiply3++;
           while(*pMutiply5*5<=pUglyNumber[NextUglyIndex])
               pMutiply5++;   
           NextUglyIndex++;
        }
     int ugly=pUglyNumber[index-1];
     delete[]pUglyNumber;
     return ugly;
     }
    
    int Min(int a,int b,int c)
      {
        int min=a; 
        if(min>b)
            min=b;
        if(min>c)
            min=c;
        return min;
      }
    /*方法一:尴尬,超时。
    int GetUglyNumber_Solution(int index) {    
    if(index<=0)
        return 0;
    int count=0;
    bool flag_ugly=false;
    int i;
    for(i=1;count!=index;i++)
        {
           if(IfUgly(i))
               count++;
        }
    return i-1;
    }
    
    bool IfUgly(int i)
     {
         int temp=i;
         while(temp%2==0)
             temp=temp/2;
         while(temp%3==0)
             temp=temp/3;
         while(temp%5==0)
             temp=temp/5;
         if(temp==1)
             return true;
         else
             return false;
     }
     */
};

发表于 2017-07-10 10:27:47 回复(1)
/**
 * 丑数
 *
 * 把只包含素因子2、3和5的数称作丑数(Ugly Number)。
 * 例如6、8都是丑数,但14不是,因为它包含因子7。
 *  习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
 * 
 *  丑数规律是前面的数*2||*3||*5都会得到一个丑数,为了避免重复 我们就想了一个办法,取当前最小的丑数然后加入丑数数组。
 * 
 *  1*2,1*3,1*5 min 2   2*2,1*3,1*5 min 3  2*2,2*3,1*5 min 4 2*2,2*3,1*5 min 5  
 * @author Boyce
 *
 */

public static int GetUglyNumber_Solution(int index) {
if (index <= 0)
return 0;
List<Integer> list = new ArrayList<>();
int i2 = 0, i3 = 0, i5 = 0;
list.add(1);
int k = 0;
int min = 0;
while (k < index) {
k++;
int num2 = list.get(i2)*2;
int num3 = list.get(i3)*3;
int num5 = list.get(i5)*5;
min = Math.min(num2, Math.min(num3, num5));
if (num2 == min)
i2++;
if (num3 == min)
i3++;
if (num5 == min)
i5++;
list.add(min);
}
return list.get(index-1);
    }

编辑于 2017-04-26 09:08:55 回复(0)
import java.util.*;
public class Solution {
    public int GetUglyNumber_Solution(int index) {
    if(index==0)return 0;
    int n=1,ugly=1,min;       
    Queue<Integer> q2=new LinkedList<Integer>();
    Queue<Integer> q3=new LinkedList<Integer>();
    Queue<Integer> q5=new LinkedList<Integer>();   
    q2.add(2);q3.add(3);q5.add(5);
    while(n!=index){
       ugly=Math.min(q2.peek(),Math.min(q3.peek(),q5.peek()));
       if(ugly==q2.peek()){
           q2.add(ugly*2);q3.add(ugly*3);q5.add(ugly*5);q2.poll();
       }
       if(ugly==q3.peek()){
           q3.add(ugly*3);q5.add(ugly*5);q3.poll();
       }
       if(ugly==q5.peek()){
           q5.add(ugly*5);q5.poll();
       }
       n++;
    }
        return ugly;
    }
}

发表于 2016-07-13 13:06:27 回复(0)
class Solution {
public:
    int GetUglyNumber_Solution(int index) {
    //动态规划,对于第i个数,它一定是之前已存在数的2倍,3倍或5倍
        if(index <= 0)
            return 0;
        int* buf = new int[index];
        buf[0] = 1;
        int s1 = 0;
        int s2 = 0;
        int s3 = 0;
        for(int i = 1;i<index;++i){
            buf[i] = min(buf[s1]*2,min(buf[s2]*3,buf[s3]*5));
            if(buf[i] == buf[s1]*2) s1++;
            if(buf[i] == buf[s2]*3) s2++;
            if(buf[i] == buf[s3]*5) s3++;
        }
        return buf[index-1];
    }
};

发表于 2017-02-06 22:10:54 回复(2)
#include <bits/stdc++.h>
using namespace std;

#define nullptr NULL

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

class Solution {
public:

    // 解法二:空间换时间
    // 用数组按顺序保存已经找到的丑数
    int GetUglyNumber_Solution(int index) {
        if(index <= 0) return 0;
        int *pUglyNumbers = new int[index];
        pUglyNumbers[0] = 1;
        int nextUglyIndex = 1;

        // 记录对应的位置
        // 我们要寻找一个丑数, 乘以2, 3, 5之后大于arr[i - 1]且这个数最小
        int *p2 = pUglyNumbers;
        int *p3 = pUglyNumbers;
        int *p5 = pUglyNumbers;
        while(nextUglyIndex < index) {
            int minUgly = getMinUgly(*p2 * 2, *p3 * 3, *p5 * 5);  // 取最小
            pUglyNumbers[nextUglyIndex] = minUgly;
            // 移动相应位置
            while(*p2 * 2 <= pUglyNumbers[nextUglyIndex]) p2++;
            while(*p3 * 3 <= pUglyNumbers[nextUglyIndex]) p3++;
            while(*p5 * 5 <= pUglyNumbers[nextUglyIndex]) p5++;
            nextUglyIndex++;  // 继续找下一个丑数
        }
        int ugly = pUglyNumbers[nextUglyIndex-1];
        delete[] pUglyNumbers;
        return ugly;
    }


    int getMinUgly(int a, int b, int c) {
        int minVal = a < b ? a : b;
        minVal = minVal < c ? minVal : c;
        return minVal;
    }

    // 解法一:
    // 按照顺序判断每个数是不是丑数
    // 缺点:即使一个数不是丑数, 还是需要对它进行计算
    int getUgly(int index) {
        if(index <= 0) return 0;
        int number = 0;
        int uglyFound = 0;
        while(uglyFound < index) {
            number++;
            if(isUgly(number))
                uglyFound++;
        }
        return number;
    }

    // 判断一个数是不是丑数
    bool isUgly(int number) {
        while(number % 2 == 0)
            number /= 2;
        while(number % 3 == 0)
            number /= 3;
        while(number % 5 == 0)
            number /= 5;
        return (number == 1) ? true : false;
    }
};


发表于 2018-03-17 20:55:08 回复(0)
import java.util.*;

public class Solution {
    public int GetUglyNumber_Solution(int index) {
         if( index == 0 ){
          return 0; 
        }
ArrayList<Integer> al = new ArrayList<Integer>();
    int count = 1;
        al.add(1);
        int min = 0;
        int m1 = 0, m3 = 0, m5 = 0;
        while(count < index){
            min = min(al.get(m1)*2, al.get(m3)*3, al.get(m5)*5);
            count++;
            al.add(min);
             if(min == al.get(m1)*2) 
                 m1++;
             if(min == al.get(m3)*3) 
                 m3++;
             if(min == al.get(m5)*5) 
                 m5++;
        }
        return al.get(index - 1);
    
    }
    
    public int min(int a, int b, int c){
        int temp = a > b? b:a;
        return temp = temp > c? c:temp;
    }
}

发表于 2015-10-08 21:45:50 回复(0)
    # 每个丑数都是由前面的某个丑数(但是并不一定恰是前一个丑数)多一个质因子得来的
    # 同时,每一个丑数增加一个质因子都是一个更大的丑数,应该排在后面(并不一定是紧挨着的后面)
    # 每个数生成的丑数都是严格按照*2、*3、*5的大小依次排列
    # 都是增加同一个质因子,则生成的序列大小顺序与原顺序一致
    # 但是不同的丑数的不同结果之间没有确定的大小顺序
    # 因此我们会对每一个已有丑数按照大小顺序依次增加一个质因子,并且比较他们之间的大小
    # 最后,丑数生成过程中由于质因子排列顺序不同会出现重叠,需要注意去重
    def GetUglyNumber_Solution(self, index):
        # write code here
        if not index: # 处理边界情况
            return 0
        res = [0,1] # 存储维护丑数序列
        i2 = i3 = i5 = 1 # 待增加相应质因子的丑数的位置,i2之前的丑数增加一个2的结果已经都入列了,因此i2是序列中增加一个2的最小的位置了,i3i5同理
        while(index-1):
            x,y,z = res[i2]*2,res[i3]*3,res[i5]*5 # 三个候选丑数
            # 选择其中最小的一个入列,并且向下遍历
            if x <= y and x <= z:
                tar = x
                i2 += 1
            elif y <= x and y <= z:
                tar = y
                i3 += 1
            else:
                tar = z
                i5 += 1
            if tar != res[-1]: # 去重操作,同样的数不多次入队
                res.append(tar)
                index -= 1
        return res[-1]
发表于 2019-06-14 15:57:25 回复(1)
function GetUglyNumber_Solution(index)
{
    if(index <=0) return 0;
    let uglyArr = [1], idx2 = idx3 = idx5 = 0, i;
    for(i = 1; i < index; ++i){
        uglyArr[i] = Math.min(uglyArr[idx2]*2, uglyArr[idx3]*3, uglyArr[idx5]*5);
        if(uglyArr[i] === uglyArr[idx2]*2) ++idx2;
        if(uglyArr[i] === uglyArr[idx3]*3) ++idx3;
        if(uglyArr[i] === uglyArr[idx5]*5) ++idx5;
    }
    return uglyArr[index-1];
}

发表于 2018-04-25 11:22:59 回复(0)
妙啊,妙啊。
public class Solution {
public static int GetUglyNumber_Solution(int index) {
        if (index == 0) return 0;
        int []res = new int[index];
        res[0] = 1;
        int i2,i3,i5;
        i2 = i3 = i5 = 0;
        for (int i = 1;i < index;i ++) {
            res[i] = Math.min(res[i2] * 2, Math.min(res[i3] * 3, res[i5] * 5));
            if (res[i] == res[i2] * 2) i2 ++;
            if (res[i] == res[i3] * 3) i3 ++;
            if (res[i] == res[i5] * 5) i5 ++;
        }
        return res[index - 1];
    }
}
发表于 2018-03-23 19:02:38 回复(1)
int Solution::GetUglyNumber_Solution(int index){
    if (index <= 0)
        return 0;
    vector<int> tmp(index);
    int NumOfUglyNumber = 0;
    tmp.at(NumOfUglyNumber++) = 1;
    int tmp2 = 0, tmp3 = 0, tmp5 = 0;
    while (NumOfUglyNumber < index){
        for (int i = 0; i < NumOfUglyNumber;i++){
             tmp2 = tmp.at(i) * 2;
             if (tmp2 > tmp.at(NumOfUglyNumber-1))
                break;
        }
        for (int i = 0; i < NumOfUglyNumber; i++){
            tmp3 = tmp.at(i) * 3;
            if (tmp3 > tmp.at(NumOfUglyNumber - 1))
                break;
        }
        for (int i = 0; i < NumOfUglyNumber; i++){
            tmp5 = tmp.at(i) * 5;
            if (tmp5 > tmp.at(NumOfUglyNumber - 1))
                break;
        }
        tmp.at(NumOfUglyNumber++) = minOfThreeNumber(tmp2,tmp3,tmp5);
    }
    return tmp.back();
}
int Solution::minOfThreeNumber(int n1, int n2, int n3){
    return n3 < ( ((n1>n2) ? n2 : n1) ) ? n3: ((n1 > n2) ? n2 : n1);
}

发表于 2018-03-16 13:18:58 回复(0)
#Python版 
#思路:3个队列,分别保存2,3,5 的倍数,依次去最小值,然后添加。
# -*- coding:utf-8 -*-
import sys
class Solution:
    def GetUglyNumber_Solution(self, index):
        # write code here
        #2,3,5
        if index <=0 :
            return 0
        if index==1:
            return 1
        queue2 = []
        queue3 = []
        queue5 = []
        queue2.append(2)
        queue3.append(3)
        queue5.append(5)
        val = 0
        for i in range(2,index+1):
            v2 = queue2[0] if len(queue2)!=0 else sys.maxint
            v3 = queue3[0] if len(queue3) !=0 else sys.maxint
            v5 = queue5[0] if len(queue5) !=0 else sys.maxint
            val = min(v2,v3,v5)
            if val == v2:
                queue2.pop(0)
                queue2.append(val*2)
                queue3.append(val*3)
            elif val ==v3:
                queue3.pop(0)
                queue3.append(val*3)
            else:
                queue5.pop(0)
            queue5.append(val *5)

        return val

print Solution().GetUglyNumber_Solution(7)

发表于 2016-12-07 11:51:44 回复(2)