2.8　分數(shù)到小數(shù)

題目描述（第166題）

給定兩個整數(shù)，分別表示分數(shù)的分子numerator和分母denominator，以字符串形式返回小數(shù)。

如果小數(shù)部分為循環(huán)小數(shù)，則將循環(huán)的部分放在括號內(nèi)。

示例1

輸入：numerator=1，denominator=2

輸出："0.5" 。

示例2

輸入：numerator=2，denominator=1

輸出："2"

示例3：

輸入：numerator=2，denominator=3

輸出："0.(6)"

思路

首先需要明確的一點是，只要是能夠被分數(shù)表示的數(shù)都是有理數(shù)。還有一點需要了解，有理數(shù)只能是有限數(shù)或無限循環(huán)小數(shù)，因此題目中不可能出現(xiàn)無限不循環(huán)的情況，也就是說問題是可解的。這道題目的難點是找出循環(huán)節(jié)，一旦找到循環(huán)節(jié)，剩下要做的就是簡單地將商的整數(shù)部分和循環(huán)節(jié)（如果存在）進行拼接。

為了厘清思路，不妨從幾個尋常的例子入手。既然問題的難點是找到循環(huán)節(jié)，那么我們直接來看一個有循環(huán)節(jié)的例子：numerator=2，denominator=3。

步驟1：讓分子除以分母。

步驟2：如果余數(shù)是0，則直接退出，否則執(zhí)行步驟3。

步驟3：把余數(shù)乘以10作為分子，分母不變，然后繼續(xù)執(zhí)行步驟1。

以2/3為例，上面的過程會無限循環(huán)，因此必須手動退出，計算出循環(huán)節(jié)并返回。上述例子中分母始終不變，分子將會是類似2,6,6,6,6,6,6,…這樣的序列，容易看出循環(huán)節(jié)是6。如何證明其正確性呢？

由于分母是不變的，因此下一個分子如果在前面序列中出現(xiàn)過，那么一定會形成循環(huán)。假設(shè)分子為m，那么理論上循環(huán)節(jié)的長度不會超過m-1。一個簡單的思路是用哈希表記錄分子出現(xiàn)的情況，如果下一個分子在之前出現(xiàn)過，我們就找到了循環(huán)節(jié)。將上一次和這一次分子出現(xiàn)的位置之間的部分（左閉右開）作為循環(huán)節(jié)即可。由于我們需要用到分子出現(xiàn)的位置信息，因此使用數(shù)組來代替哈希表，不過這對于結(jié)果來說并不重要。如果愿意你也可以使用哈希表。

代碼

最終結(jié)果由兩部分組成，分別是符號和值。簡單起見，首先取絕對值，計算出值部分。然后通過二者相除是否大于0計算出符號部分。

復雜度分析

●　時間復雜度：由于seen數(shù)組的長度最多為denominator-1，我們最多執(zhí)行denominator-1次循環(huán)體，因此時間復雜度為。

●　空間復雜度：由于seen數(shù)組的長度最多為denominator-1，因此空間復雜度為。