计算数组中的不同值 - C++

Question

我正在尝试自学(重新学习)C++并通过在线书籍和测试来解决问题以获得一些练习.我遇到了这个让我有点困惑的问题.我怎么会最好的呢？

我必须写一个函数

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

返回数组A中不同值的数量.我可以假设数组范围是0到100,000.并且元素都是+或 - 1,000,000的整数.有任何想法吗？我正在考虑循环并计算每个值,但这可能效率非常低吗？提前致谢.

Answer 1

编辑更新:包含空间优化算法以及娱乐

您可以使用std :: set来包含唯一值.只需将数组元素复制到一个集合中(无论如何你喜欢),然后计算集合中唯一元素的数量.

这是一个相当简洁的代码,它甚至不需要你指定数组的大小(但是,通常在c ++中你std::vector仍然会使用它):

在http://ideone.com/rpWGS上查看(包含测试数据和输出)

#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; 
     }

};

Answer 2

您的解决方案相当有效(事实上,就时间复杂度而言,尽可能高效),但在空间中 - 要计算值,您需要一个大小与可能值范围相对应的数组,以便计算实例在100,000个项目的数组中,您需要一个约2,000,000个项目的辅助数组(范围从-1,000,000到1,000,000).

您有两种方法可以避免/减少这种情况.一种是为每个可能的输入存储一位,并在看到该输入时设置该位.这具有相同的基本复杂性,但是将计数空间减少到必要的最小值(即,您并不关心任何输入发生了多少次,只是它是否发生).在C++中,显而易见的方法是std::vector<bool>.虽然经常vector<bool>受到诽谤,但在这种情况下,却完全符合您的要求.

另一种可能性是使用从输入数字到计数/比特的稀疏映射.特别是当您的范围远大于输入数量时,这可以节省相当多的空间(所占用的空间将与输入数量成比例,而不是范围).在C++中,显而易见的方法是std::set<int>.为了保持相同的预期复杂度(O(N)而不是O(N log N),您需要使用unordered_set替代.

另一种可能性是对输入进行排序,然后消除重复.这通常使辅助存储器保持最小,但通常需要稍长的时间来执行(O(N log N)而不是O(N)).对于这一点,你可能会使用std::vector,std::sort和std::unique.