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

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

简单的修改有助于消除一半的迭代，但复杂度仍然是二次的。

似乎没有办法更快地解决这个问题（使用因式分解等）

 make v: vector of A.size zeros
 ...
      for(int j=i+1;j<A.size();j++){
         if(A[j]%A[i]==0 || A[i]%A[j]==0){
             increment v[i] and v[j]

Answer 2

对于is divided by，引用每个元素的计数；找到每个元素的除数并添加任何匹配项的计数。

对于divides，引用每个可见除数的计数；添加元素的任何匹配项的计数。

O(n * sqrt m) 其中 m 是最大值（输入）。

Answer 3

我不确定是否可以解决你的问题，但是像

这样的问题怎么样

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;
}

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

然后您可以遍历输入数组并将每个数字的因数添加到映射中，并继续添加它们作为因数的数字索引。例如如果 num 为 6，则将 1、2 和 3 添加到输入数组中索引为 6 的映射中。对所有数字执行此操作。

现在，遍历输入数组，然后为每个数字检查它是否在 indexedFactors 映射中，并在所有这些索引处递增结果数组中的计数。这会处理 divides 部分。此外，增加每个时间的计数以处理除以部分。例如如果 num 为 2，则输入数组中的索引为 4 和 6，并且这些索引将在结果数组中更新。但是因为 2 除以 4，所以 4 也可以被 2 整除，因此增加结果数组中索引为 2 的计数。

复杂度为O(n * m)，其中m是输入数组中每个数字的因子数(~√num)。

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

Given an array,find the number of element it can divide or divided by the remaining elements of the array

c++

algorithm

vector

dynamic-programming

data-structures