-2

我正在解决有关LeetCode的以下问题：

编写一个接受整数 n 并返回其因子的所有可能组合的函数。例如，12应该返回：
[
   [2, 6],
   [2, 2, 3],
   [3, 4]
]

我想出了以下方法（在 C++ 中）：

class Solution {
public:
    vector<vector<int>> getFactors(int n) {
        if(n==0 || n==1) return vector<vector<int>>();

        vector<vector<int>> result;
        vector<int> factors;
        getFactorsUtil(result, factors, n, 2);

        return result;
    }

    void getFactorsUtil(vector<vector<int>>& result, vector<int>& factors, int n, int start) {
        long int each=1;
        for(int i=0; i<factors.size(); i++)
            each = each*factors[i];
        if(each==n) result.push_back(factors);
        if(each>n) return;

        for(int i=start; i<=n; i++) {
            if(n%i==0) {        //perfectly divisible
                factors.push_back(i);
                getFactorsUtil(result, factors, n, i);
                factors.pop_back();
            }
        }
    }
};

这按预期工作，但在最后一个测试用例上超时：23848713.

一种被接受和赞成的解决方案（在 Java 中）如下：

public List<List<Integer>> getFactors(int n) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    helper(result, new ArrayList<Integer>(), n, 2);
    return result;
}

public void helper(List<List<Integer>> result, List<Integer> item, int n, int start){
    if (n <= 1) {
        if (item.size() > 1) {
            result.add(new ArrayList<Integer>(item));
        }
        return;
    }

    for (int i = start; i <= n; ++i) {
        if (n % i == 0) {
            item.add(i);
            helper(result, item, n/i, i);
            item.remove(item.size()-1);
        }
    }
}

两个代码的时间复杂度是相同的（在我看来）。那么为什么我的代码失败而其他代码成功运行23848713呢？我的意思是，我的代码中是否有一些明显的错误，还是在线法官有问题？

我感谢您的帮助。

编辑：<=n我for loop condition之前的代码中没有（只是因为其他代码有它 - 根据问题实际上并不需要它）。我后来把它包括在内。但无论如何，它仍然超时。

Edit2：在大 O 表示法中，我们跳过 的系数n。我认为这就是它在这里中断的原因。我的代码中这些常量的值很大。我想不出其他解释。

4

1 回答 1

0

由于第一个循环（我在其中计算所有数字的乘积factors）each，我的代码高于O(n). 因此，它失败了。

但是，当我用 value n/i（而不是n）调用它时，我可以通过消除整个循环来完全摆脱 O(n) 因素。之所以如此，是因为我不再需要检查产品是否等于n.

因此，由于这种变化，代码最终被接受。谢谢。

（发布，因为它可能对某人有帮助）。另外，感谢@user4581301最终导致我这样做的提示。

于 2018-01-08T23:28:30.393 回答