【試題描述】我們把只包含因子2、3和5的數稱作丑數。求按從到大的順序的第1500個丑數。例如6,8是丑數，而14不是，因為它包含因子7.習慣上把1當作第一個丑數。

?????? 根據丑數的定義，丑數應該是另一個丑數乘以2、3或者5的結果（1除外）。因此我們可以創建一個數組，里面的數字是排好序的丑數。里面的每一個丑數是前面的丑數乘以2、3或者5得到的。那關鍵就是確保數組里的丑數是有序的了。我們假設數組中已經有若干個丑數，排好序后存在數組中。

????? 接下來我們換一種思路來分析這個問題，試圖只計算丑數，而不在非丑數的整數上花費時間。根據丑數的定義，丑數應該是另一個丑數乘以2、3或者5的結果（1除外）。因此我們可以創建一個數組，里面的數字是排好序的丑數。里面的每一個丑數是前面的丑數乘以2、3或者5得到的。

?

這種思路的關鍵在于怎樣確保數組里面的丑數是排好序的。我們假設數組中已經有若干個丑數，排好序后存在數組中。我們把現有的最大丑數記做M。現在我們來生成下一個丑數，該丑數肯定是前面某一個丑數乘以2、3或者5的結果。我們首先考慮把已有的每個丑數乘以2。在乘以2的時候，能得到若干個結果小于或等于M的。由于我們是按照順序生成的，小于或者等于M肯定已經在數組中了，我們不需再次考慮；我們還會得到若干個大于M的結果，但我們只需要第一個大于M的結果，因為我們希望丑數是按從小到大順序生成的，其他更大的結果我們以后再說。我們把得到的第一個乘以2后大于M的結果，記為M₂。同樣我們把已有的每一個丑數乘以3和5，能得到第一個大于M的結果M₃和M₅。那么下一個丑數應該是M₂、M₃和M₅三個數的最小者。

?

前面我們分析的時候，提到把已有的每個丑數分別都乘以2、3和5，事實上是不需要的，因為已有的丑數是按順序存在數組中的。對乘以2而言，肯定存在某一個丑數T₂，排在它之前的每一個丑數乘以2得到的結果都會小于已有最大的丑數，在它之后的每一個丑數乘以2得到的結果都會太大。我們只需要記下這個丑數的位置，同時每次生成新的丑數的時候，去更新這個T₂。對乘以3和5而言，存在著同樣的T₃和T₅。

?

【參考代碼】

?

1 int Min(int a, int b, int c) { 2 3 return (a < b ? a : b) < c ? (a < b ? a : b) : c; 4 } 5 6 int uglyNumber(int n) { 7 8 if(n <= 0) { 9 throw ("Invalid Input."); 10 } 11 12 long* uglyNum = new long[n]; 13 uglyNum[0] = 1; 14 15 int index2 = 0; 16 int index3 = 0; 17 int index5 = 0; 18 int indexLast = 0; 19 20 while(indexLast < n) { 21 int min = Min(uglyNum[index2] * 2, uglyNum[index3] * 3, uglyNum[index5] * 5); 22 uglyNum[++indexLast] = min; 23 24 while(uglyNum[index2] * 2 <= uglyNum[indexLast]) { 25 index2++; 26 } 27 28 while(uglyNum[index3] * 3 <= uglyNum[indexLast]) { 29 index3++; 30 } 31 32 while(uglyNum[index5] * 5 <= uglyNum[indexLast]) { 33 index5++; 34 } 35 } 36 37 return uglyNum[n - 1]; 38 39 } 40 41

?

總結

以上是生活随笔為你收集整理的【IT笔试面试题整理】丑数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。