劍指Offer面試題：29.丑數(shù)
題目：我們把只包含因子2、3和5的數(shù)稱作丑數(shù)（Ugly Number）。求按從小到大的順序的第1500個丑數(shù)。例如6、8都是丑數(shù)，但14不是，因為它包含因子7。習慣上我們把1當做第一個丑數(shù)。
一、題目：丑數(shù)
題目：我們把只包含因子2、3和5的數(shù)稱作丑數(shù)（Ugly Number）。求按從小到大的順序的第1500個丑數(shù)。例如6、8都是丑數(shù)，但14不是，因為它包含因子7。習慣上我們把1當做第一個丑數(shù)。
二、兩種解決方案
2.1 一一遍歷法：時間效率低下
使用遍歷法求第k個丑數(shù)，從1開始遍歷，如果是丑數(shù)則count++，直到count=k為止。那么如何判斷丑數(shù)呢？根據(jù)丑數(shù)的定義，丑數(shù)只有2，3，5這三個因子，那么我們就拿數(shù)字除以這三個因子。具體算法如下：
Step1.如果一個數(shù)能夠被2整除，那么讓他繼續(xù)除以2；
Step2.如果一個數(shù)能夠被3整除，那么讓他繼續(xù)除以3；
Step3.如果一個數(shù)能夠被5整除，那么讓他繼續(xù)除以5；
Step4.如果最后這個數(shù)變?yōu)?，那么這個數(shù)就是丑數(shù)，否則不是。
根據(jù)以上算法實現(xiàn)代碼如下：
public int GetUglyNumber(int index) { if (index <= 0) { return 0; } int number = 0; int uglyCount = 0; while (uglyCount < index) { number++; if (IsUgly(number)) { uglyCount++; } } return number; } private 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; }
該算法非常直觀，代碼也非常簡潔，但最大的問題就在于每個整數(shù)都需要計算。即使一個數(shù)字不是丑數(shù)，我們還是需要對它做求余數(shù)和除法操作。因此該算法的時間效率不是很高，
2.2 空間換時間法：時間效率較高
根據(jù)丑數(shù)的定義，我們可以知道丑數(shù)可以由另外一個丑數(shù)乘以2，3或者5得到。因此我們可以創(chuàng)建一個數(shù)組，里面的數(shù)字是排好序的丑數(shù)，每一個丑數(shù)都是前面的丑數(shù)乘以2，3或者5得到的。
我們把得到的第一個丑數(shù)乘以2以后得到的大于M的結果記為M2。同樣，我們把已有的每一個丑數(shù)乘以3和5，能得到第一個大于M的結果M3和M5。那么M后面的那一個丑數(shù)應該是M2,M3和M5當中的最小值：Min(M2,M3,M5)。比如將丑數(shù)數(shù)組中的數(shù)字按從小到大乘以2，直到得到第一個大于M的數(shù)為止，那么應該是2*2=4<M，3*2=6>M，所以M2=6。同理，M3=6，M5=10。所以下一個丑數(shù)應該是6。
根據(jù)以上思路實現(xiàn)代碼如下：
public int GetUglyNumber(int index) { if (index <= 0) { return 0; } int[] uglyNumbers = new int[index]; uglyNumbers[0] = 1; int nextUglyIndex = 1; int multiply2 = 0; int multiply3 = 0; int multiply5 = 0; int min = 0; while (nextUglyIndex < index) { min = Min(uglyNumbers[multiply2] * 2, uglyNumbers[multiply3] * 3, uglyNumbers[multiply5] * 5); uglyNumbers[nextUglyIndex] = min; while (uglyNumbers[multiply2] * 2 <= uglyNumbers[nextUglyIndex]) { multiply2++; } while (uglyNumbers[multiply3] * 3 <= uglyNumbers[nextUglyIndex]) { multiply3++; } while (uglyNumbers[multiply5] * 5 <= uglyNumbers[nextUglyIndex]) { multiply5++; } nextUglyIndex++; } int result = uglyNumbers[index - 1]; uglyNumbers = null; return result; } private int Min(int num1, int num2, int num3) { int min = num1 < num2 ? num1 : num2; min = min < num3 ? min : num3; return min; }
和第一種方案相比，第二種方案不需要在非丑數(shù)的整數(shù)上做任何計算，因此時間效率有明顯提升。但也需要指出，第二種算法由于需要保存已經(jīng)生成的丑數(shù)，因此需要一個數(shù)組，從而增加了空間消耗。如果是求第1500個丑數(shù)，將創(chuàng)建一個能容納1500個丑數(shù)的數(shù)組，這個數(shù)組占內(nèi)存6KB。
三、單元測試與性能對比
3.1 單元測試
?。?）測試用例
public static void Main(string[] args) { Program p = new Program(); p.Test(1); p.Test(2); p.Test(3); p.Test(4); p.Test(5); p.Test(6); p.Test(7); p.Test(8); p.Test(9); p.Test(10); p.Test(11); p.Test(1500); p.Test(0); p.Test(1500); Console.ReadKey(); } public void Test(int index) { int result = GetUglyNumberWithSpace(index); Console.WriteLine("Test result is {0}", result); Console.WriteLine("-------------End-------------"); }
（2）測試結果
3.2 性能對比
這里我們使用兩種解決方案來求第1500個丑數(shù)，通過下面的圖片可以清楚地看到兩種方案的響應時間。（這里借助老趙的CodeTimer類來進行時間效率的監(jiān)測）
?。?）一一遍歷法：65秒，我等得花兒都謝了
（2）空間換時間法：4毫秒，迅雷不及掩耳
由對比可以看出，一個簡單的優(yōu)化，再通過6KB的空間換取了巨大的時間效率，在實際開發(fā)中是一個值得實踐的解決思路（當然，事先得權衡一下利弊）。
作者：周旭龍
出處：http://edisonchou.cnblogs.com
本文版權歸作者和博客園共有，歡迎轉(zhuǎn)載，但未經(jīng)作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文鏈接。
浙公網(wǎng)安備 33010602011771號