1447.最简分数

1、题干

给你一个整数 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、解法1-哈希表

用哈希映射存储小数和分数字符串，其中小数作为键分数字符串作为值，最后返回哈希映射中的所有值

3、代码

var simplifiedFractions = function (n) {
    const map = new Map();
    for (let i = 1; i < n; i++) {
        for (let j = i + 1; j <= n; j++) {
            if (!map.has(i / j)) map.set(i / j, `${i}/${j}`);
        }
    }

    return [...map.values()];
};

4、复杂度

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n)$

5、执行结果

• 执行用时: 108 ms
• 内存消耗: 46.3 MB

6、解法2-求公约数

参考求素数的方法，从 $2$ 开始遍历到 $\sqrt{n}$，看分子分母是否存在公约数

7、代码

var simplifiedFractions = function (n) {
    function skip(min, max) {
        for (let i = 2; i * i <= max; i++) {
            if (max % i === 0 && (min % i === 0 || min % (max / i) === 0)) return true;
        }
        return false;
    }

    const res = [];
    for (let i = 1; i < n; i++) {
        for (let j = i + 1; j <= n; j++) {
            if (!skip(i, j)) res.push(i + '/' + j);
        }
    }

    return res;
};

8、复杂度

• 时间复杂度：$O(n^2*\sqrt{n})$
• 空间复杂度：$O(n)$

9、执行结果

• 执行用时: 88 ms
• 内存消耗: 47.2 MB

10、解法3-分母因数倍乘+哈希集合

参考求素数的方法，从 $2$ 开始遍历到 $\sqrt{n}$，求出所有小于分母的因数及其倍乘结果并存储到哈希集合 cdSet 中，若分子存在于 cdSet 中则说明分子分母存在公约数

11、代码

var simplifiedFractions = function (n) {
    const res = [];
    for (let i = 2; i <= n; i++) {
        const cdSet = new Set();
        for (let c = 2; c * c <= i; c++) {
            if (i % c) continue;
            for (let m = 1; m * c < i; m++) {
                cdSet.add(m * c);
                if (m * i / c < i) cdSet.add(m * i / c);
            }
        }

        for (let j = 1; j < i; j++) {
            if (!cdSet.has(j)) res.push(j + '/' + i);
        }
    }

    return res;
};

12、复杂度

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n)$

13、执行结果

• 执行用时: 84 ms
• 内存消耗: 46.9 MB