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

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

我不确定你的问题是否有可能，但是像

namespace {
    std::unordered_map<int, std::vector<size_t>> const factors{
        {1, {1}},
        {2, {1}},
        {3, {1}},
        {4, {1, 2}},
        {5, {1}},
        {6, {1, 2, 3}},
    };
}

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

您可以有一个预先计算的数字及其因数表(代码中的 factors)。不要将数字本身作为自身的一个因素添加到列表中。
然后你可以迭代输入数组并将每个数字的因子添加到映射中，并继续添加它们作为因子的数字的索引。例如如 num是 6，然后将 1、2 和 3 添加到映射中，输入数组中的索引为 6。对所有数字执行此操作。
现在，遍历输入数组，然后检查每个数字是否在 indexedFactors 中。在所有这些索引处映射并增加结果数组中的计数。这会处理除法部分。此外，增加这些时间中的每一个的计数以处理除以部分。例如如 num如果为 2，则输入数组中的索引为 4 和 6，这些索引将在结果数组中更新。但是由于 2 除以 4，因此 4 也可以被 2 整除，因此在索引 2 处增加结果数组中的计数。
复杂度是 O(n * m)哪里 m是输入数组中每个数字的因子数 (~ √num )。