给定一个数组，找出它可以除以或除以数组剩余元素的元素数

Question

Input Array: int A={2,3,4,5,6} , array is not always sorted.

output Array:{2,1,1,0,2}

• 因为我们可以看到A[0]可以除以 4 & 6 所以它有输出 2。
• A[1] 只能除以 6，它有输出 1。
• A[2] 除以 2，所以输出 1。
• A[3] 无法进行除法或被除法，因此输出为 0。
• A[4] 正被 2 & 3 除，所以输出 2。

我能够使用时间复杂度为 o(n*n) 的蛮力方法来解决它。什么可能是解决它的最有效方法。谢谢你。我的代码：

    #include<iostream>
    #include<vector>
    using namespace std;
    //Function to return output vector
    vector<int>solve(vector<int> &A) {
        vector<int>v;
        for(int i=0;i<A.size();i++){
            int count=0;
            for(int j=0;j<A.size();j++){
                if(i!=j){
                    if(A[j]%A[i]==0 || A[i]%A[j]==0){
                        count++;
                    }
                }
            }
            v.push_back(count);
        }
        return v;
    }
    
    int main(){
        vector<int>v={2,3,4,5,6};
        vector<int>s;
        s=solve(v);
    //printing the output array
        for(int i=0;i<s.size();i++){
            cout<<s[i]<<" ";
        }
    }

---

Answer 1

我不确定你的问题是否可能，但是像这样的事情怎么样

\n

namespace {\n    std::unordered_map<int, std::vector<size_t>> const factors{\n        {1, {1}},\n        {2, {1}},\n        {3, {1}},\n        {4, {1, 2}},\n        {5, {1}},\n        {6, {1, 2, 3}},\n    };\n}\n\nstd::vector<int>solve(std::vector<int> &A) {\n    std::unordered_map<int, std::vector<size_t>> indexedFactors;\n    size_t idx = 0;\n    for(auto num: A) {\n        // Lookup the factors of num from the table\n       for(auto factor: factors.at(num)) {\n           //  and add them to the map with indexes pointing to the number that has them as a factor\n           indexedFactors[factor].push_back(idx);\n       }\n       ++idx;\n    }\n    std::vector<int> res(A.size());\n    idx = 0;\n    for(auto num: A) {\n        if (indexedFactors.find(num) != indexedFactors.end()) {\n            for(auto i: indexedFactors.at(num)) {\n                res[i]++; // Track the divides\n                res[idx]++; // Track the divided by\n            }\n        }\n        ++idx;\n    }\n    return res;\n}\n

\n

您可以有一个预先计算的数字及其因子表（factors在代码中）。不要将数字本身作为其自身因素添加到列表中。

\n

然后，您可以迭代输入数组，并将每个数字的因子添加到映射中，并继续添加它们作为因子的数字的索引。例如，如果num是 6，则将 1、2 和 3 添加到输入数组中索引为 6 的映射中。对所有数字都这样做。

\n

现在，迭代输入数组，然后对于每个数字检查它是否在映射中，indexedFactors并在所有这些索引处增加结果数组中的计数。这解决了划分部分。另外，增加每次的计数以处理除以部分。例如，如果num为 2，则输入数组中将具有索引 4 和 6，并且这些索引将在结果数组中更新。但由于 2 能除 4，因此 4 也能被 2 整除，因此增加结果数组中索引 2 处的计数。

\n

复杂度是O(n * m)其中m是输入数组 (~ ) 中每个数字的因子数\xe2\x88\x9anum。

\n