2.8　分数到小数

题目描述（第166题）

给定两个整数，分别表示分数的分子numerator和分母denominator，以字符串形式返回小数。

如果小数部分为循环小数，则将循环的部分放在括号内。

示例1

输入：numerator=1，denominator=2

输出："0.5" 。

示例2

输入：numerator=2，denominator=1

输出："2"

示例3：

输入：numerator=2，denominator=3

输出："0.(6)"

思路

首先需要明确的一点是，只要是能够被分数表示的数都是有理数。还有一点需要了解，有理数只能是有限数或无限循环小数，因此题目中不可能出现无限不循环的情况，也就是说问题是可解的。这道题目的难点是找出循环节，一旦找到循环节，剩下要做的就是简单地将商的整数部分和循环节（如果存在）进行拼接。

为了厘清思路，不妨从几个寻常的例子入手。既然问题的难点是找到循环节，那么我们直接来看一个有循环节的例子：numerator=2，denominator=3。

步骤1：让分子除以分母。

步骤2：如果余数是0，则直接退出，否则执行步骤3。

步骤3：把余数乘以10作为分子，分母不变，然后继续执行步骤1。

以2/3为例，上面的过程会无限循环，因此必须手动退出，计算出循环节并返回。上述例子中分母始终不变，分子将会是类似2,6,6,6,6,6,6,…这样的序列，容易看出循环节是6。如何证明其正确性呢？

由于分母是不变的，因此下一个分子如果在前面序列中出现过，那么一定会形成循环。假设分子为m，那么理论上循环节的长度不会超过m-1。一个简单的思路是用哈希表记录分子出现的情况，如果下一个分子在之前出现过，我们就找到了循环节。将上一次和这一次分子出现的位置之间的部分（左闭右开）作为循环节即可。由于我们需要用到分子出现的位置信息，因此使用数组来代替哈希表，不过这对于结果来说并不重要。如果愿意你也可以使用哈希表。

代码

最终结果由两部分组成，分别是符号和值。简单起见，首先取绝对值，计算出值部分。然后通过二者相除是否大于0计算出符号部分。

复杂度分析

●　时间复杂度：由于seen数组的长度最多为denominator-1，我们最多执行denominator-1次循环体，因此时间复杂度为。

●　空间复杂度：由于seen数组的长度最多为denominator-1，因此空间复杂度为。