数组中的计数不同的值 - C ++ [英] Count distinct values in an array - C++

问题描述

我想教我（重新学习）C ++和做从书本和测试问题在网上得到一些做法。我碰到这个问题，这给我留下了有点困惑。我将如何去最好呢？

I'm trying to teach myself (re-learn) C++ and doing problems from books and tests online to get some practice. I came across this problem which has left me a little confused. How would I best go about it?

我必须写一个函数

class Solution { public int distinct (int [] A); }

，返回在阵列A的不同值的数目
我可以假设该阵列范围是0到100000。而且该元素是被+或所有整数 - 100。
有任何想法吗？我想通过循环，并为每个值进行计数，但是这可能是真正的无效率吗？先谢谢了。

that returns the number of distinct values in the array A. I can assume that the array range is 0 to 100,000. And that the elements are all integers which are + or - 1,000,000. Any ideas? I was thinking of looping through and counting up for each value but that's probably really inefficient right? Thanks in advance.

推荐答案

修改更新：包括优化空间的算法也只是为了好玩。

Edit Updated: included a space-optimized algorithm as well just for fun

您可以使用一个std ::设置为包含唯一值。只需复制数组元素为一组（反正你喜欢），并计算从集合事后独特元素的数量。

You can use a std::set to contain the unique values. Just copy the array elements into a set (anyway you like), and count the number of unique elements from the set afterwards.

下面是code的相当简洁一点，不需要你甚至指定数组（虽然大小，通常在C ++中你会使用的std ::矢量反正）：

Here is a rather succinct bit of code that doesn't require you to even specify the size of the array (though, normally in c++ you'd be using a std::vector anyway):

查看它生活在 http://ideone.com/rpWGS （其中包含测试数据和输出）

See it live on http://ideone.com/rpWGS (which contains test data and output)

#include <set>

class Solution 
{ 
   public: 

     // using std::set (max O(n) additional storage)
     template<size_t N>
         static size_t distinct (int (&a)[N])
     {
         return std::set<int>(a, a+N).size();
     }

     // using std::unique (inplace mutation; no additional storage)
     template<size_t N> 
         static size_t distinct_optim(int (&a)[N])
     {
         std::sort(a, a+N);
         int* newend = std::unique(a, a+N);
         return newend - a; 
     }

};

这篇关于数组中的计数不同的值 - C ++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！