使用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++在数组中找到不同的元素

回答

相关问题