подсчитать количество различных абсолютных значений среди элементов массива

Question

Мне задали вопрос на собеседование, чтобы найти количество различных абсолютных значений среди элементов массива. Я придумал следующее решение (на 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();
}

Answer 1

Как сказал @Jerry, чтобы немного улучшить тему большинства других ответов, вместо использования std :: map или std :: set вы можете использовать std :: unordered_map или std :: unordered_set (или эквивалент буста).

Это уменьшило бы время работы с O (n lg n) или O (n).

Еще одна возможность, в зависимости от диапазона предоставленных данных, вы могли бы сделать вариант радикальной сортировки, хотя в этом вопросе нет ничего, что бы сразу указывало на это.

Answer 2

Я думаю, std::map также может быть интересным:

int absoluteDistinct(const vector<int> &A) 
{
    map<int, char> my_map;

    for (vector<int>::const_iterator it = A.begin(); it != A.end(); it++)
    {
        my_map[abs(*it)] = 0;
    }

    return my_map.size();
}

Answer 3

Чтобы ответить на ваш второй вопрос первым, да, код - O(n^2), поскольку сложность find равна O(n).

У вас есть варианты, чтобы улучшить его.Если диапазон чисел невелик, вы можете просто установить достаточно большой массив и счетчик приращений при переборе исходных данных.Если диапазон больше, но редок, вы можете использовать хеш-таблицу для подсчета.Обе эти опции имеют линейную сложность.

В противном случае я бы сделал одну итерацию, чтобы взять значение abs каждого элемента, затем отсортировать их, а затем вы можете выполнить агрегацию за один дополнительный проход.Сложность здесь n log(n) для сортировки.Другие проходы не имеют значения для сложности.