Как сохранить только дубликаты?

Question

Учитывая вектор STL, выведите только дубликаты в отсортированном порядке, например,

INPUT : { 4, 4, 1, 2, 3, 2, 3 }
OUTPUT: { 2, 3, 4 }

Алгоритм тривиален, но цель состоит в том, чтобы сделать его таким же эффективным, как std :: unique (). Моя наивная реализация изменяет контейнер на месте:

Моя наивная реализация:

void not_unique(vector<int>* pv)
{
    if (!pv)
        return;

 // Sort (in-place) so we can find duplicates in linear time
 sort(pv->begin(), pv->end());

 vector<int>::iterator it_start = pv->begin();
 while (it_start != pv->end())
 {
  size_t nKeep = 0;

  // Find the next different element
  vector<int>::iterator it_stop = it_start + 1;
  while (it_stop != pv->end() && *it_start == *it_stop)
  {
   nKeep = 1; // This gets set redundantly
   ++it_stop;
  }

  // If the element is a duplicate, keep only the first one (nKeep=1).
  // Otherwise, the element is not duplicated so erase it (nKeep=0).
  it_start = pv->erase(it_start + nKeep, it_stop);
 }
}

Если вы можете сделать это более эффективным, элегантным или общим, пожалуйста, дайте мне знать. Например, пользовательский алгоритм сортировки или копирование элементов во 2-м цикле для исключения вызова erase ().

Answer 1

Я потерпел неудачу с первой попыткой, предполагая, что std::unique перемещает все дубликаты в конец диапазона (это не так). К сожалению. Вот еще одна попытка:

Вот реализация not_unique. Он удаляет любые элементы, которые появляются только один раз в отсортированном диапазоне и , дубликатов любых элементов, которые появляются более одного раза. Таким образом, полученный диапазон представляет собой уникальный список элементов, которые появляются более одного раза.

Функция имеет линейную сложность и выполняет один проход в диапазоне (std::unique имеет линейную сложность). It должен соответствовать требованиям прямого итератора. Конец результирующего диапазона возвращается.

template <typename It>
It not_unique(It first, It last)
{
    if (first == last) { return last; }

    It new_last = first;
    for (It current = first, next = ++first; next != last; ++current, ++next)
    {
        if (*current == *next)
        {
            if (current == new_last)
            {
                ++new_last;
            }
            else
            {
                *new_last++ = *current;
                while (next != last && *current == *next)
                {
                    ++current;
                    ++next;
                }
                if (next == last)
                    return new_last;
            }
        }
    }
    return new_last;
}

Answer 2

Вы можете даже использовать несоответствие, для дополнительных очков!
Кстати: хорошее упражнение.

template<class TIter>
/** Moves duplicates to front, returning end of duplicates range.
 *  Use a sorted range as input. */
TIter Duplicates(TIter begin, TIter end) {
    TIter dup = begin;
    for (TIter it = begin; it != end; ++it) {
        TIter next = it;
        ++next;
        TIter const miss = std::mismatch(next, end, it).second;
        if (miss != it) {
            *dup++ = *miss;
            it = miss;
        }
    }
    return dup;
}

Answer 3

Короче и больше STL-иш, чем предыдущие записи. Предполагается отсортированный ввод.

#include <algorithm>
#include <functional>

template< class I, class P >
I remove_unique( I first, I last, P pred = P() ) {
    I dest = first;
    while (
        ( first = std::adjacent_find( first, last, pred ) )
            != last ) {
        * dest = * first;
        ++ first;
        ++ dest;
        if ( ( first = std::adjacent_find( first, last, std::not2( pred ) ) )
            == last ) break;
        ++ first;
    }
    return dest;
}

template< class I >
I remove_unique( I first, I last ) {
    return remove_unique( first, last,
        std::equal_to< typename std::iterator_traits<I>::value_type >() );
}

Answer 4

Это в стиле стандартной библиотеки. Кредит на алгоритм переходит к Джеймсу ! (Если вы +1 мне, вам лучше +1 ему, или иначе ). Все, что я сделал, это сделал его стандартным стилем библиотеки:

#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <vector>

// other stuff (not for you)
template <typename T>
void print(const char* pMsg, const T& pContainer)
{
    std::cout << pMsg << "\n    ";
    std::copy(pContainer.begin(), pContainer.end(),
        std::ostream_iterator<typename T::value_type>(std::cout, " "));
    std::cout << std::endl;
}

template <typename T, size_t N>
T* endof(T (&pArray)[N])
{
    return &pArray[0] + N;
}

// not_unique functions (for you)
template <typename ForwardIterator, typename BinaryPredicate>
ForwardIterator not_unique(ForwardIterator pFirst, ForwardIterator pLast,
                           BinaryPredicate pPred)
{
    // correctly handle case where an empty range was given:
    if (pFirst == pLast) 
    { 
        return pLast; 
    }

    ForwardIterator result = pFirst;
    ForwardIterator previous = pFirst;

    for (++pFirst; pFirst != pLast; ++pFirst, ++previous)
    {
        // if equal to previous
        if (pPred(*pFirst, *previous))
        {
            if (previous == result)
            {
                // if we just bumped bump again
                ++result;
            }
            else if (!pPred(*previous, *result))
            {
                // if it needs to be copied, copy it
                *result = *previous;

                // bump
                ++result;
            }
        }
    }

    return result;
}

template <typename ForwardIterator>
ForwardIterator not_unique(ForwardIterator pFirst, ForwardIterator pLast)
{
    return not_unique(pFirst, pLast,
                std::equal_to<typename ForwardIterator::value_type>());
}


//test
int main()
{
    typedef std::vector<int> vec;

    int data[] = {1, 4, 7, 7, 2, 2, 2, 3, 9, 9, 5, 4, 2, 8};
    vec v(data, endof(data));

    // precondition
    std::sort(v.begin(), v.end());
    print("before", v);

    // duplicatify (it's a word now)
    vec::iterator iter = not_unique(v.begin(), v.end());
    print("after", v);

    // remove extra
    v.erase(iter, v.end());
    print("erased", v);
}

Answer 5

Мое предложение будет измененной сортировкой вставок, чтобы вы могли одновременно сортировать и фильтровать дубликаты.

Answer 6

Еще один:

template <typename T>
void keep_duplicates(vector<T>& v) 
{
    set<T> 
        u(v.begin(), v.end()), // unique 
        d; // duplicates
    for (size_t i = 0; i < v.size(); i++)
        if (u.find(v[i]) != u.end())
            u.erase(v[i]);
        else
            d.insert(v[i]);

    v = vector<T>(d.begin(), d.end());
}

Answer 7

Вызов "стереть (it_start + keep, it_stop);" из цикла while будет происходить копирование оставшихся элементов снова и снова.

Я бы предложил перенести все уникальные элементы в начало вектора, а затем стереть все оставшиеся элементы сразу.

int num_repeats(vector<int>::const_iterator curr, vector<int>::const_iterator end) {
  int same = *curr;
  int count = 0;
  while (curr != end && same == *curr) {
    ++curr;
    ++count;
  }
  return count;
}

void dups(vector<int> *v) {
  sort(v->begin(), v->end());
  vector<int>::iterator current = v->begin();
  vector<int>::iterator end_of_dups = v->begin();
  while (current != v->end()) {
    int n = num_repeats(current, v->end());
    if (n > 1) {
      swap(*end_of_dups, *current);
      end_of_dups++;
    }
    current += n;
  }
  v->erase(end_of_dups, v->end());
}

Answer 8

Я думаю, что с большой точки зрения O, он реализован настолько хорошо, насколько это возможно. Переопределяющая стоимость - это сорт, который равен O (N log N). Одной из возможностей, однако, было бы создание нового вектора с дублирующимися записями, а не использование существующего вектора с операцией удаления, удаляющей недубликаты. Тем не менее, это было бы лучше, если отличное количество дубликатов мало по отношению к общему количеству записей.

Рассмотрим крайний пример. Если исходный массив состоит из 1000 записей с одним дубликатом, то на выходе будет вектор с одним значением. Возможно, будет немного эффективнее создать новый вектор с одной записью, чем удалять остальные 999 записей из исходного вектора. Однако я подозреваю, что при тестировании в реальном мире экономию этого изменения может быть трудно измерить.

Редактировать Я просто думал об этом с точки зрения вопроса об интервью. Другими словами, это не очень полезный ответ. Но было бы возможно решить это за O (N) (линейное время), а не O (N Log N). Используйте место для хранения вместо процессора. Создайте два "битных" массива, очистив их изначально Переберите ваш вектор целочисленных значений. Посмотрите каждое значение в первом битовом массиве. Если он не установлен, установите бит (установите его на 1). Если он установлен, тогда установите соответствующий бит во втором массиве (указывая на дубликат). После обработки всех векторных записей просканируйте второй массив и выведите целые числа, которые являются дубликатами (обозначены битами, установленными во втором битовом массиве). Причиной использования битовых массивов является просто космическая эффективность. Если речь идет о 4-байтовых целых числах, то необработанное пространство должно быть (2 * 2^32 / 8 ). Но на самом деле это можно превратить в полезный алгоритм, сделав его разреженным массивом. Сам псевдо-псевдокод будет выглядеть примерно так:

bitarray1[infinite_size];
bitarray2[infinite_size];

clear/zero bitarrays

// NOTE - do not need to sort the input
foreach value in original vector {
    if ( bitarray1[value] ) 
        // duplicate
        bitarray2[value] = 1
    bitarray1[value] = 1
}

// At this point, bitarray2 contains a 1 for all duplicate values.
// Scan it and create the new vector with the answer
for i = 0 to maxvalue
    if ( bitarray2[i] )
        print/save/keep i

Answer 9

Что подразумевается под "столь же эффективным, как std :: unique"? Эффективен с точки зрения времени выполнения, времени разработки, использования памяти или как?

Как отмечали другие, для std :: unique требуется отсортированный ввод, который вы не предоставили, поэтому с самого начала это не честный тест.

Лично я бы хотел, чтобы std :: map делал всю мою работу за меня. У этого есть много свойств, которые мы можем использовать для максимальной элегантности / краткости. Он сохраняет свои элементы отсортированными, и оператор [] вставит нулевое значение, если ключ еще не существует. Используя эти свойства, мы можем сделать это в две или три строки кода и при этом достичь разумной сложности во время выполнения.

По сути, мой алгоритм таков: для каждого элемента в векторе увеличивайте на единицу запись карты, указав значение этого элемента. После этого просто пройдитесь по карте, выводя любой ключ, значение которого больше 1. Не может быть проще.

#include <iostream>
#include <vector>
#include <map>

void
output_sorted_duplicates(std::vector<int>* v)
{
   std::map<int, int> m;  

   // count how many of each element there are, putting results into map
   // map keys are elements in the vector, 
   // map values are the frequency of that element
   for (std::vector<int>::iterator vb = v->begin(); vb != v->end(); ++vb)
      ++m[*vb];

   // output keys whose values are 2 or more
   // the keys are already sorted by the map
   for (std::map<int, int>::iterator mb = m.begin(); mb != m.end(); ++mb)
      if ( (*mb).second >= 2 ) 
         std::cout << (*mb).first << " "; 
   std::cout << std::endl;
}

int main(void) 
{ 
   int initializer[] = { 4, 4, 1, 2, 3, 2, 3 };
   std::vector<int> data(&initializer[0], &initializer[0] + 7);
   output_sorted_duplicates(&data);
}

janks@phoenix:/tmp$ g++ test.cc && ./a.out
2 3 4

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

Создание моей функции как шаблона и приведение его в действие в диапазонах в стиле STL, а не только в векторах целых, оставлено в качестве упражнения.

Answer 10

Это исправляет ошибки в оригинальной версии Джеймса МакНеллиса. Я также предоставляю версии на месте и вне места.

// In-place version.  Uses less memory and works for more container
// types but is slower.
template <typename It>
It not_unique_inplace(It first, It last)
{
    if (first == last)
        return last;

    It new_last = first;
    for (It current = first, next = first + 1; next != last; ++current, ++next)
    {
        if (*current == *next && 
            (new_last == first || *current != *(new_last-1)))
            *new_last++ = *current;
    }
    return new_last;
}

// Out-of-place version. Fastest.
template <typename It, typename Container>
void not_unique(It first, It last, Container pout)
{
    if (first == last || !pout)
        return;

    for (It current = first, next = first + 1; next != last; ++current, ++next)
    {
        if (*current == *next && 
            (pout->empty() || *current != pout->back()))
            pout->push_back(*current);
    }
}