如何有效地只保留重复项？

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

如果您可以使其更加高效、优雅或通用，请告诉我。例如，自定义排序算法，或复制第二个循环中的元素以消除擦除（）调用。

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

比以前的条目更短、更接近 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 3

您甚至可以使用不匹配来获得额外积分！
顺便说一句：很好的锻炼。

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 4

我的建议是修改插入排序，以便您可以排序和排序。同时过滤欺骗。

Answer 5

这是标准库的风格。算法的功劳归功于 James！ （如果你+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 6

调用“erase(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 7

我认为，从大 O 的角度来看，你已经尽可能地实现了它。最重要的成本是排序，其时间复杂度为 O(N log N)。不过，一种可能性是使用重复条目构建一个新向量，而不是使用现有向量并通过删除操作删除非重复项。然而，只有当重复的不同数量相对于条目总数较小时，这才会更好。

考虑一下极端的例子。如果原始数组由 1,000 个条目组成，只有一个重复项，那么输出将是一个只有一个值的向量。使用一个条目创建新向量可能比从原始向量中删除其他 999 个条目更有效。然而，我怀疑在现实世界的测试中，这种改变所节省的成本可能很难衡量。

编辑我只是在考虑“面试”问题。换句话说，这不是一个非常有用的答案。但可以在 O(N)（线性时间）而不是 O(N Log N) 内解决这个问题。使用存储空间代替CPU。创建两个“位”数组，最初将它们清除。循环遍历整数值向量。查找第一位数组中的每个值。如果未设置，则设置该位（将其设置为 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 8

另一张：

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 9

这修复了 James McNellis 原始版本中的错误。我还提供就地和异地版本。

// 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);
    }
}

Answer 10

“与 std::unique 一样高效”是什么意思？在运行时、开发时间、内存使用等方面高效吗？

正如其他人指出的那样， std::unique 需要排序输入，而您尚未提供，因此这不是一个公平的测试。

就我个人而言，我只会让 std::map 为我完成所有工作。它有很多属性，我们可以使用它来实现最大程度的优雅/简洁。它保持其元素已排序，如果键尚不存在，operator[] 将插入零值。通过利用这些属性，我们可以用两到三行代码完成此任务，并且仍然实现合理的运行时复杂性。

基本上，我的算法是这样的：对于向量中的每个元素，将由该元素的值键入的映射条目加一。然后，简单地遍历地图，输出任何值大于 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 样式范围上运行，而不仅仅是整数向量，这将作为练习。