题目描述

给你一个整数 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

算法

(暴力枚举) $O(n²·logn)$

1. 遍历所有 2 ~ n 的分母，找出所有与分母互质的分子记录到答案里。
2. 互质： 公约数只有1的两个整数，叫做互质整数

时间复杂度

• 第一层循环需要遍历一遍所有分母, 时间复杂度为 $O(n)$
• 第二层循环需要遍历一遍所有分子, 时间复杂度最坏为 $O(n)$
• 一次欧几里得算法的时间复杂度为 $O(logn)$ 这个证明可以看看网上
• 最后，时间复杂度为 $O(n²·logn)$

空间复杂度

• 所有分子分母的组合总共有 1 + 2 + 3 + ... + n 个, 存储需要使用 $O(n²)$

C++ 代码

class Solution {
public:

    int gcd(int a, int b) {
        return b ? gcd(b, a % b) : a;
    } 

    vector<string> simplifiedFractions(int n) {

        vector<string> ans;

        for (int i = 2; i <= n; i ++)
            for (int j = 1; j < i; j ++)
                if (gcd(i, j) == 1)
                    ans.push_back(to_string(j) + "/" + to_string(i));

        return ans;
    }
};