热门文章
 当前位置：技术文章 > 编程面试题 >

计算数组元素之间不同的绝对值的数量

问题内容：

我被问到一个面试问题，以找出数组元素之间不同的绝对值的数量。我想出了以下解决方案（使用C ++），但访问员对代码的运行时效率不满意。

  1. 我将对如何提高此代码的运行时效率的指针表示赞赏。
  2. 另外，我如何计算下面代码的效率？该for循环执行A.size()时间。但是我不确定STL的效率std::find（在更坏的情况下，可能O(n)会使代码如此O(n²)？

代码是：

int countAbsoluteDistinct ( const std::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()是线性的（O（n））。我将使用排序的关联容器来处理此问题，特别是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();
}

这种方法仍然有一些运行时损失。随着容器大小的增加，使用单独的容器会产生动态分配的成本。您可以就地执行此操作，而不会造成这种损失，但是对于处于此级别的代码，有时最好使其清晰明了，并让优化器（在编译器中）执行其工作。