Блог

 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> amp;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]<<" ";
        }
    }
 

Я не уверен, возможно ли это для вашей проблемы, но как насчет чего-то вроде

 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> amp;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 ).

Простая модификация помогает удалить половину итераций, но сложность остается квадратичной.

Кажется, что нет способа решить эту проблему быстрее (с факторизацией и т. Д.)

  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]
 

Например is divided by , укажите количество каждого элемента; найдите делители каждого элемента и добавьте количество любых совпадений.

Для divides ссылки на количество каждого видимого делителя; добавьте количество любых совпадений элемента.

O(n * кв. м), где m-макс(вход).