使用C++在數組中找到不同的元素

我有一個整數數組。我想用C++在數組中找到所有不同的元素。 solutin 1：蠻力使用嵌套循環，該解決方案的複雜度是O（n^2）使用C++在數組中找到不同的元素

溶液2：排序這將需要O（n日誌N）

是否有任何其他技術，該技術能比O（n Log n）給出更好的結果？任何其他數據結構或任何不同的技術？

來源

2015-08-22 Vishal Sharma

由不同的你的意思，那有頻率1？ –

使用std::unordered_set將是O（n）。

來源

2015-08-22 04:54:05 Arcinde

散列表的*平均*複雜度是O（n），而不是最壞的情況。當O（n）最大時，可以做到這一點。整數已知並且足夠小。 – Jens

@Jens哈希表插入是O（1）*攤銷*，這是一個比一般情況更強有力的保證。無法找到「最差情況」的輸入，其插入的序列（足夠長）的平均插入比O（1）更差。 – Arcinde

-1

如果你知道最大整數，並且它相當小，你不能分配一個大的向量並用它來計算每個整數的頻率。然後，迭代向量，並找到所有與頻率之一：

template<typename I> 
auto findWithFrequency(int f, int max, I first, I last) 
{ 
    std::vector<int> counts(max, 0); 
    for(; first != last; ++first) 
    { 
     counts[*first] += 1; 
    } 

    std::vector<typename I::value_type> v; 
    v.reserve(std::distance(first, last)); 

    std::copy_if(counts.begin(), counts.end(), 
       std::back_inserter(v), 
       [f](auto x) {return x == f;}); 

    return v; 
}

在最壞的情況下，這需要在輸入數組的大小的陣列兩次迭代，所以複雜性爲O（n）。

這實質上是Bucketsort或Radix背後的想法。

來源

2015-08-22 09:08:40 Jens

您的技術是否減少時間少於。 O（n Log n）。也許HASH會有所幫助。 – sam

@sam我不明白你的意見。該算法首先迭代輸入數組，即O（n）。然後迭代桶數組，這也是O（n）。散列函數在哪裏提供幫助？散列表的複雜度平均爲O（n），但Bucketsort或Radixsort的最壞情況複雜度爲O（n）。 – Jens

下降者會評論爲什麼-1？我認爲這是一個限制整數的合理方法。 – Jens

您也可以嘗試使用std::nth_element：它部分地排序範圍[第一，第n，最後），使得區間[第一，第n個]中的所有條目都是< =第n個，並且所有元素間隔（第n個，最後一個）> =第n個。它具有線性複雜度（O（n）），並會在序列中找到第n個元素。不過，它不適合找到具體的號碼，所以也許它不是你所需要的。但值得記住:-)

來源

2015-08-22 11:35:31 dhaumann

使用C++在數組中找到不同的元素

回答

相關問題