计算数组中的不同值 - 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到100,000。并且元素都是+或 - 1,000,000的整数。
任何想法？我想的循环和计数每个值，但这可能是真正低效的权利吗？提前感谢。

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 :: set包含唯一值。只需将数组元素复制到一个集合中（无论何时你喜欢），然后计算从集合中的唯一元素的数量。

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.

这里是一个相当简洁的代码不要求你甚至指定数组的大小（虽然，通常在c + +你使用 std :: vector 反正）：

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屋！