计数阵列的元件之间不同的绝对值的数 [英] count the number of distinct absolute values among the elements of the array

问题描述

有人问我的采访问题找不同的绝对值的数组的元素中有多少。我想出了以下解决方案（在C ++中），但面试官很不满意code的运行时的效率。

1. 我会AP preciate指标，让我怎么能改善这个code运行时的效率？

2. 另外我如何计算低于code中的效率？ for循环执行A.size（）倍。但是我不知道STL发现的效率（在最坏的情况下，它可能是为O（n），这样就使得这个code O（N2）？

     INT absoluteDistinct（常量矢量＆lt; INT＆GT;＆安培; A）{
   
   使用名字空间std;
   名单＆LT;诠释＆GT; X;
   
   矢量＆lt; INT＆GT; ::为const_iterator它;
   对于（IT = A.begin（）;它＆LT; A.end（）;它++）{
     如果（找到（x.begin（），x.end（），ABS（*它））== x.end（））{
       x.push_back（ABS（*吧））;
     }
   }
   
   返回x.size（）;
    

   }

解决方案

的std ::发现（）是线性（O（N））。我会使用一个排序关联容器来处理这个问题，特别是的std ::设置。

 的#include＆LT;载体＆GT;
＃包括＆LT;集＆gt;
使用名字空间std;

诠释distict_abs（常量矢量＆lt; INT＆GT;＆安培;ⅴ）
{
   的std ::设为＆LT; INT＆GT; distinct_container;

   为（自动curr_int = v.begin（），结束= V.END（）; //不需要调用V.END（）多次
       curr_int =结束！;
       ++ curr_int）
   {
       //的std ::设为只允许单个条目
       //因为这是我们想要的，我们不在乎失败
       //如果相同值的第二（或更多）被试图
       //插入。
       distinct_container.insert（绝对（* curr_int））;
   }

   返回distinct_container.size（）;
}
 

还有一些运行时的惩罚这种做法。用一个单独的容器即被动态分配作为容器尺寸的增加的成本。你可以在这个层面做的地方，而不是出现这个点球，但是与code它有时更是清晰，明确并且让优化器（在编译器）完成其工作。

I was asked an interview question to find the number of distinct absolute values among the elements of the array. I came up with the following solution (in C++) but the interviewer was not happy with the code's run time efficiency.

1. I will appreciate pointers as to how I can improve the run time efficiency of this code?

2. Also how do I calculate the efficiency of the code below? The for loop executes A.size() times. However I am not sure about the efficiency of STL find (In the worse case it could be O(n) so that makes this code O(n2) ?

   int absoluteDistinct ( const vector<int> &A ) {
   
   using namespace std;
   list<int> x;
   
   vector<int>::const_iterator it;
   for(it = A.begin();it < A.end();it++){
     if(find(x.begin(),x.end(),abs(*it)) == x.end()){
       x.push_back(abs(*it));
     }
   }
   
   return x.size();
   

   }

解决方案

std::find() is linear (O(n)). I'd use a sorted associative container to handle this, specifically std::set.

#include <vector>
#include <set>
using namespace std;

int distict_abs(const vector<int>& v)
{
   std::set<int> distinct_container;

   for(auto curr_int = v.begin(), end = v.end(); // no need to call v.end() multiple times
       curr_int != end;
       ++curr_int)
   {
       // std::set only allows single entries
       // since that is what we want, we don't care that this fails 
       // if the second (or more) of the same value is attempted to 
       // be inserted.
       distinct_container.insert(abs(*curr_int));
   }

   return distinct_container.size();
}

There is still some runtime penalty with this approach. Using a separate container incurs the cost of dynamic allocations as the container size increases. You could do this in place and not occur this penalty, however with code at this level its sometimes better to be clear and explicit and let the optimizer (in the compiler) do its work.

这篇关于计数阵列的元件之间不同的绝对值的数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！