把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第 n个丑数。
数据范围:
要求:空间复杂度 , 时间复杂度
通俗易懂的解释:首先从丑数的定义我们知道,一个丑数的因子只有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; } };
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的最小的
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]; } }
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]; }