LC.P1447[最简分数]

方法一：数学

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public List<String> simplifiedFractions(int n) {
        List<String> ans = new ArrayList<>();
        for (int i = 1; i < n; ++i) {
            for (int j = i + 1; j <= n; ++j) {
                if (gcd(i, j) == 1) ans.add(i + "/" + j);
            }
        }
        return ans;
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}
  • 时间复杂度：$O(n^2logn)$
  • 空间复杂度：$O(1)$