LeetCode -- Ugly Number II

LeetCode -- Ugly Number II

題目描述：
Write a program to find the n-th ugly number.


Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.


Note that 1 is typically treated as an ugly number.


本題算是Ugly number 1的擴展問題，求出第n個ugly number。


本題屬於數學問題，回顧一下ugly number的定義：因數只包含2,3,5的數和1。






方法一：
基於Ugly number 1中的函數IsUgly，逐個判斷從1到n，累計到第n個ugly的number即可。缺點很顯然，逐個判斷效率非常低。


方法二：


對於任意1個大於2,3,5的ugly number 來說，除以2,3,5後必然仍是ugly number，可使用哈希來緩存ugly number ，每次除以2,3,5判斷是否在哈希中有鍵值。
這種方式使用了大量的空間，並且很多多余的判斷浪費在了不是ugly number上。
本解法依然無法被AC。


實現代碼：

public int NthUglyNumber(int n) 
{
	var hash = new Dictionary();
	hash.Add(1 , 1);
	hash.Add(2 , 2);
	hash.Add(3 , 3);
	hash.Add(4 , 4);
	hash.Add(5 , 5);
	if(hash.ContainsKey(n)){
		return hash[n];
	}
	var count = 5;
	var n1 = 6;
	while(count < n){
		if(n1 % 2 == 0 && hash.ContainsKey(n1/2) ||
		   n1 % 3 == 0 && hash.ContainsKey(n1/3) ||
		   n1 % 5 == 0 && hash.ContainsKey(n1/5)){
			hash.Add(n1, count);
			count ++;
		}
		n1++;
	}
	
	return hash.Keys.Last();
}

方法三：
1.由於是計算第n個ugly number，那麼它一定來自於由2,3,5分別出發的3個序列中的其中某個元素。
2.可使用2,3,5三個變量來記錄當前序列出發的最小ugly數，每次取得這3個序列中的最小那個，然後從2,3,5序列取出下一位ugly數。


本實現參考了：
http://www.geeksforgeeks.org/ugly-numbers/
http://www.cnblogs.com/grandyang/p/4743837.html


實現代碼：

public class Solution {
    public int NthUglyNumber(int n) 
    {
    	var i2 = 1;
    	var i3 = 1;
    	var i5 = 1;
    	var uglies = new List();
    	uglies.Add(1);
    	while (uglies.Count < n) {
    		var v2 = uglies[i2-1] * 2;
    		var v3 = uglies[i3-1] * 3;
    		var v5 = uglies[i5-1] * 5;
    		
    		int min = Math.Min(v2, Math.Min(v3, v5));
    		if (min == v2) {
    			i2++;
    		}
    		if (min == v3){
    			i3++;
    		}
    		if (min == v5) {
    			i5++;
    		}
    		uglies.Add(min);
    	}
    	return uglies.Last();
    }
}