通俗易懂的解释：

首先从丑数的定义我们知道，一个丑数的因子只有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;
    }
};

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] 

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

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];
    }
}

#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];
}