把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第 n个丑数。
数据范围:
要求:空间复杂度 , 时间复杂度
class Solution { public: int GetUglyNumber_Solution(int index) { if(index<=0) return 0; queue<int> q2; queue<int> q3; queue<int> q5; int i=1; int count=1; while(count<index) { q2.push(i*2); q3.push(i*3); q5.push(i*5); int min2=q2.front(); int min3=q3.front(); int min5=q5.front(); int min=(min2>min3)?min3:min2; min=(min>min5)?min5:min; cout<<i<<endl; if(min2==min) q2.pop(); if(min3==min) q3.pop(); if(min5==min) q5.pop(); i=min; count++; } return i; } };
通俗易懂的解释:首先从丑数的定义我们知道,一个丑数的因子只有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 22 |4|3 6|5 10目前指针指向1,0,0,队列头arr[1] * 2 = 4, arr[0] * 3 = 3, arr[0] * 5 = 5(3)1 2 32| 4 63 |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; } };
/* 说下思路,如果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; } }
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的最小的
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; }
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; }
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; } */ };
# -*- 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]
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
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); } }
}
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; } }
# 每个丑数都是由前面的某个丑数(但是并不一定恰是前一个丑数)多一个质因子得来的 # 同时,每一个丑数增加一个质因子都是一个更大的丑数,应该排在后面(并不一定是紧挨着的后面) # 每个数生成的丑数都是严格按照*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]
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]; } };
public class Solution { public int GetUglyNumber_Solution(int index) { if(index==0)return 0; int[] res=new int[index]; int t2=0,t3=0,t5=0; res[0]=1; for(int i=1;i<index;i++){ res[i]=Math.min(Math.min(res[t2]*2,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]; } }丑数的定义是1或者因子只有2 3 5,可推出丑数=丑数*丑数,假定丑数有序序列为:a1,a2,a3.......an
#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; } };
#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)
}
/////////很常规,很通用的思路;虽然通不过 public class Solution { public int GetUglyNumber_Solution(int index) { if(index<=0){ return 0; } int num=0; int uglyFound=0; while(uglyFound<index){ num++; if(isUgly(num)){ uglyFound++; } } return num; } private static boolean isUgly(int num){ while(num%2==0){ num=num/2; } while(num%3==0){ num=num/3; } while(num%5==0){ num=num/5; } return num==1; } } ////////这个题的思路真是非常的牛逼,不容易想到 public class Solution { public int GetUglyNumber_Solution(int index) { if(index<=0){ return 0; } int[] arr=new int[index]; int t2=0,t3=0,t5=0; arr[0]=1; int temp; for(int i=1;i<index;i++){ temp=min(2*arr[t2],min(3*arr[t3],5*arr[t5])); arr[i]=temp; if(arr[t2]*2==temp) t2++; if(arr[t3]*3==temp) t3++; if(arr[t5]*5==temp) t5++; } return arr[index-1]; } public static int min(int a,int b){ return a<b?a:b; } }
public class Solution { public int GetUglyNumber_Solution(int index) { if (index < 7) return index; // 7也是质因子,前面的数都是丑数 int[] arr = new int[index]; arr[0] = 1; int t1 = 0, t2 = 0, t3 = 0; for (int i = 1; i < index; ++i) { arr[i] = Math.min(arr[t1] * 2, Math.min(arr[t2] * 3, arr[t3] * 5)); if (arr[i] == arr[t1] * 2) ++t1; if (arr[i] == arr[t2] * 3) ++t2; if (arr[i] == arr[t3] * 5) ++t3; } return arr[index - 1]; } }