### 题目描述 给你一个整数 n ，请你返回所有 0 到 1 之间（不包括 0 和 1）满足分母小于等于 n 的 最简 分数 。分数可以以 任意 顺序返回。 ### 输入输出 #### 示例1 ``` 输入：n = 2 输出：["1/2"] 解释："1/2" 是唯一一个分母小于等于 2 的最简分数。 ``` #### 示例2 ``` 输入：n = 3 输出：["1/2","1/3","2/3"] ``` #### 示例3 ``` 输入：n = 4 输出：["1/2","1/3","1/4","2/3","3/4"] 解释："2/4" 不是最简分数，因为它可以化简为 "1/2" 。 ``` ### 示例4 ``` 输入：n = 1 输出：[] ``` **提示：** 1 <= n <= 100 ### 题目解答 ####思路 生成以2为分母，3为分母...n为分母的分数，每次生成时候，判断分子和分母是否互质，如果互质的话将其添加到结果中去。 **互质判断——辗转相除** 辗转相除法用于寻找2个数的最大公约数。如果分子分母2个数字的最大公约数是1，那么这个分数就是最简分数。 ``` 假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里得算法，是这样进行的： 1997 / 615 = 3 (余 152) 615 / 152 = 4(余7) 152 / 7 = 21(余5) 7 / 5 = 1 (余2) 5 / 2 = 2 (余1) 2 / 1 = 2 (余0) 至此，最大公约数为1 以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数 ``` 这里编程实现求2个数字的最大公约数，可以如下所示： ```java public int mgcd(int a, int b){ // 调整2个数字，使得a大b小 if(a < b){ int t = a; a = b; b = t; } // 直到可以整除 while(a % b > 0){ int ret = a % b; a = b; b = ret; } return b; } ``` **算法复杂度** 时间复杂度： 1 生成n需要判断$$(1 + (n-1)) \times (n-1) / 2$$次判断最大公约数。 2 最大公约数判断,欧几里得算法复杂度，证明为，1.618为黄金分割比例，$$log{(1.618a+b)}$$ 因此，整体时间复杂度为$$O(n^2log{n})$$ 空间复杂度： 只需要常数记录中间变量，$$O(1)$$ 最后编辑：2024年04月23日 ©著作权归作者所有 赞 0 分享
最新回复