有效限制合併兩個列表

Question

我想合併兩個數組/列表，其中每個數組元素必須進行比較。如果他們兩個都有相同的元素，我會將它們的總數增加1。這些數組都是2D的，其中每個元素都有一個計數器用於出現。我知道這兩個數組都可以與O（n^2）中的double for for循環進行比較，但是我受O（nlogn）的限制。最終的陣列將所有來自這兩個列表中的元素與其增加櫃檯的，如果有一個以上發生

Array A[][] = [[8,1],[5,1]] 
Array B[][] = [[2,1],[8,1]] 

合併完成後，我應該得到一個數組，像這樣

Array C[][] = [[2,1],[8,2],[8,2],[5,1]] 

的元素的排列不是必須的。

從閱讀材料中，Mergesort需要O(nlogn)來合併兩個列表，但是我目前處於一個與我綁定的問題的障礙。任何僞代碼視覺將不勝感激。

Answer 1

我很喜歡Stepanov's Efficient Programming雖然他們比較慢。在會議6和7中（如果我沒有記錯的話），他討論了算法add_to_counter()和reduce_counter()。當然，這兩種算法都是微不足道的，但可以用來實現非遞歸合併分類，而不需要太多的工作。唯一可能的非顯而易見的見解是組合操作可以將兩個元素減少爲一個序列而不僅僅是一個元素。爲了實現這些操作，您實際上將使用合適的類來存儲迭代器（即數組中的指針）以表示數組的局部視圖。

我還沒有看過第7次會議之後的會議（實際上甚至沒有完成第7次會議），但我完全認爲他實際上介紹瞭如何使用會話7中產生的counter來實現合併-分類。當然，合併分類的運行時複雜度爲O(n ln n)，使用計數器方法時，它將使用O(ln n)輔助空間。

Answer 2

您可以編寫一個算法來合併它們，方法是按順序按順序遍歷兩個序列，並在適當的位置插入。

我選擇一個（貌似更貼切）數據結構在這裏：std::map<Value, Occurence>：

#include <map> 
using namespace std; 

using Value  = int; 
using Occurence = unsigned; 
using Histo  = map<Value, Occurence>; 

如果你堅持連續的存儲，boost::flat_map<>這裏應該是你的朋友（和簡易替換）。

算法（與你的輸入測試，閱讀說明註釋）：

void MergeInto(Histo& target, Histo const& other) 
{ 
    auto left_it = begin(target), left_end = end(target); 
    auto right_it = begin(other), right_end = end(other); 
    auto const& cmp = target.value_comp(); 

    while (right_it != right_end) 
    { 
     if ((left_it == left_end) || cmp(*right_it, *left_it)) 
     { 
      // insert at left_it 
      target.insert(left_it, *right_it); 
      ++right_it; // and carry on 
     } else if (cmp(*left_it, *right_it)) 
     { 
      ++left_it; // keep left_it first, so increment it 
     } else 
     { 
      // keys match! 
      left_it->second += right_it->second; 
      ++left_it; 
      ++right_it; 
     } 
    } 
} 

這真的很直截了當！

測試程序：看到它Live On Coliru

#include <iostream> 

// for debug output 
static inline std::ostream& operator<<(std::ostream& os, Histo::value_type const& v) { return os << "{" << v.first << "," << v.second << "}"; } 
static inline std::ostream& operator<<(std::ostream& os, Histo const& v) { for (auto& el : v) os << el << " "; return os; } 
// 

int main(int argc, char *argv[]) 
{ 
    Histo A { { 8, 1 }, { 5, 1 } }; 
    Histo B { { 2, 1 }, { 8, 1 } }; 

    std::cout << "A: " << A << "\n"; 
    std::cout << "B: " << B << "\n"; 

    MergeInto(A, B); 
    std::cout << "merged: " << A << "\n"; 
} 

印刷：

A: {5,1} {8,1} 
B: {2,1} {8,1} 
merged: {2,1} {5,1} {8,2} 

---

你可以洗牌接口的情況下，一點點你真的想要合併到一個新的對象（C）：

// convenience 
Histo Merge(Histo const& left, Histo const& right) 
{ 
    auto copy(left); 
    MergeInto(copy, right); 
    return copy; 
} 

現在你可以只寫

Histo A { { 8, 1 }, { 5, 1 } }; 
Histo B { { 2, 1 }, { 8, 1 } }; 
auto C = Merge(A, B); 

請參閱Live on Coliru, too

Answer 3

一個簡單的算法，需要兩倍的內存將訂購兩個輸入端（O（N日誌N）），然後從兩個列表的頭部順序選取元素並進行合併（O（n））。總的成本將是爲O（n log n）的用O（n）的額外內存

Answer 4

這裏（最小的兩個輸入額外的大小）是基於桶計數

我的算法

時間複雜度：O（N）

存儲器複雜度：O（最大），其中max是陣列中的最大元件

輸出： [8,2] [5,1] [2,1] [8,2]

代碼：

#include <iostream> 
#include <vector> 
#include <iterator> 

int &refreshCount(std::vector<int> &counters, int in) { 
    if((counters.size() - 1) < in) { 
     counters.resize(in + 1); 
    } 
    return ++counters[in]; 
} 

void copyWithCounts(std::vector<std::pair<int, int> >::iterator it, 
        std::vector<std::pair<int, int> >::iterator end, 
        std::vector<int> &counters, 
        std::vector<std::pair<int, int&> > &result 
        ) { 
    while(it != end) { 
     int &count = refreshCount(counters, (*it).first); 
     std::pair<int, int&> element((*it).first, count); 
     result.push_back(element); 
     ++it; 
    } 
} 

void countingMerge(std::vector<std::pair<int, int> > &array1, 
        std::vector<std::pair<int, int> > &array2, 
        std::vector<std::pair<int, int&> > &result) { 
    auto array1It = array1.begin(); 
    auto array1End = array1.end(); 
    auto array2It = array2.begin(); 
    auto array2End = array2.end(); 

    std::vector<int> counters = {0}; 

    copyWithCounts(array1It, array1End, counters, result); 
    copyWithCounts(array2It, array2End, counters, result); 
} 

int main() 
{ 
    std::vector<std::pair<int, int> > array1 = {{8, 1}, {5, 1}}; 
    std::vector<std::pair<int, int> > array2 = {{2, 1}, {8, 1}}; 

    std::vector<std::pair<int, int&> > result; 
    countingMerge(array1, array2, result); 

    for(auto it = result.begin(); it != result.end(); ++it) { 
     std::cout << "[" << (*it).first << "," << (*it).second << "] "; 
    } 

    return 0; 
} 

簡短說明： 因爲你提到過，那最後的安排是沒有必要的，我做了簡單的合併（沒有排序，誰要求排序？）與計數，其中結果包含對計數器的引用，所以不需要走過數組來更新計數器。