從大數據集的m個數組元素中提取n個最低總和

Question

假設您有一些包含整數的未排序數組。你的工作是創建數組的總和。總和必須從每個陣列包含正好一個值，即（3個陣列）

sum = array1[2]+array2[12]+array3[4]; 

目標：您應輸出20個的組合產生最低可能的和。

下面的解決方案是禁用的，因爲算法需要能夠處理10個可以包含大量整數的數組。以下解決方案的方式，對於大數量的陣列太慢：

//You already have int array1, array2 and array3 
int top[20]; 
for(int i=0; i<20; i++) 
    top[i] = 1e99; 

int sum = 0; 
for(int i=0; i<array1.size(); i++)  //One for loop per array is trouble for 
    for(int j=0; j<array2.size(); j++) //increasing numbers of arrays 
     for(int k=0; k<array3.size(); k++) 
     { 
     sum = array1[i] + array2[j] + array3[k]; 
     if (sum < top[19]) 
      swapFunction(sum, top); //Function that adds sum to top 
            //and sorts top in increasing order 
     } 

printResults(top); // Outputs top 20 lowest sums in increasing order 

你會怎麼做更有效地實現正確的結果（以較低的大O符號）？

Answer 1

答案可以通過考慮如何找到絕對最低總和以及如何找到第二低總和等來找到。

由於您最多隻需要20個和，您最多隻需要來自每個陣列的最低20個值。我建議使用std::partial_sort。

其餘的應該可以用一個priority_queue來完成，其中每個元素包含當前的總和以及這個總和的數組的指示。只需取每個索引的索引並將其增加1，計算新的索引並將其添加到優先級隊列中。隊列中最頂端的項目應始終是最低的項目之一。刪除最低總和，生成下一個可能性，然後重複，直到您有足夠的答案。

假設所需答案的數目遠小於大O應主要是partial_sort的效率（N + K *日誌（K））*陣列

的數量這裏的一些基本代碼來演示理念。有很多方法可以改善這一點。例如，我敢肯定，通過一些工作，您可以避免多次添加同一套指示，並且通過消除對「即時彈出」的需求。

for (size_t i = 0; i < arrays.size(); i++) 
{ 
    auto b = arrays[i].begin(); 
    partial_sort(b, b + numAnswers, arrays[i].end()); 
} 

struct answer 
{ 
    answer(int s, vector<int> i) 
     : sum(s), indices(i) 
    { 
    } 

    int sum; 
    vector<int> indices; 

    bool operator <(const answer &o) const 
    { 
     return sum > o.sum; 
    } 
}; 

auto getSum =[&arrays](const vector<int> &indices) { 
    auto retval = 0; 
    for (size_t i = 0; i < arrays.size(); i++) 
    { 
     retval += arrays[i][indices[i]]; 
    } 
    return retval; 
}; 

vector<int> initalIndices(arrays.size()); 

priority_queue<answer> q; 
q.emplace(getSum(initalIndices), initalIndices); 

for (auto i = 0; i < numAnswers; i++) 
{ 
    auto ans = q.top(); 
    cout << ans.sum << endl; 

    do 
    { 
     q.pop(); 
    } while (!q.empty() && q.top().indices == ans.indices); 

    for (size_t i = 0; i < ans.indices.size(); i++) 
    { 
     auto nextIndices = ans.indices; 
     nextIndices[i]++; 
     q.emplace(getSum(nextIndices), nextIndices); 
    } 
}