Сохраняйте только дублированные значения - Векторы C ++

Question

Предположим, у меня есть вектор со следующими элементами {1, 1, 2, 3, 3, 4}. Я хочу написать программу с кодом c ++, чтобы удалить уникальные значения и сохранить только дублированные один раз. Таким образом, конечный результат будет примерно таким: {1,3}.

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

vector <int> g1 = {1,1,2,3,3,4}
vector <int> g2;

for(int i = 0; i < g1.size(); i++)
{
  if(count(g1.begin(), g1.end(), g1[i]) > 1)
    g2.push_back(g1[i]);

}

v.erase(std::unique(g2.begin(), g2.end()), g2.end());

for(int i = 0; i < g2.size(); i++)
{
  cout << g2[i];
}

Answer 1

Мой подход заключается в создании шаблона в стиле <algorithm> и использовании unordered_map для подсчета. Это означает, что вы перебираете список ввода только один раз, а временная сложность составляет O(n). Тем не менее, он использует O(n) дополнительной памяти и не особенно удобен для кэширования. Также это предполагает, что тип во вводе является хэшируемым.

#include <algorithm>
#include <iostream>
#include <iterator>
#include <unordered_map>

template <typename InputIt, typename OutputIt>
OutputIt copy_duplicates(
        InputIt  first,
        InputIt  last,
        OutputIt d_first)
{
    std::unordered_map<typename std::iterator_traits<InputIt>::value_type,
                       std::size_t> seen;
    for ( ; first != last; ++first) {
        if ( 2 == ++seen[*first] ) {
            // only output on the second time of seeing a value
            *d_first = *first;
            ++d_first;
        }
    }
    return d_first;
}

int main()
{
    int i[] = {1, 2, 3, 1, 1, 3, 5}; // print 1, 3,
    //                  ^     ^
    copy_duplicates(std::begin(i), std::end(i),
                    std::ostream_iterator<int>(std::cout, ", "));
}

Это может выводить на любой вид итератора. Существуют специальные итераторы, которые вы можете использовать для записи значения в контейнер.

Answer 2

Вот способ, который немного более удобен для кэша, чем unordered_map ответ, но это O (n log n) вместо O (n), хотя он не использует никакой дополнительной памяти и не выделяет. Кроме того, общий множитель, вероятно, выше, несмотря на удобство кэширования.

#include <vector>
#include <algorithm>

void only_distinct_duplicates(::std::vector<int> &v)
{
    ::std::sort(v.begin(), v.end());
    auto output = v.begin();
    auto test = v.begin();
    auto run_start = v.begin();
    auto const end = v.end();
    for (auto test = v.begin(); test != end; ++test) {
       if (*test == *run_start) {
           if ((test - run_start) == 1) {
              *output = *run_start;
              ++output;
           }
       } else {
           run_start = test;
       }
    }
    v.erase(output, end);
}

Я проверял это, и оно работает. Если вы хотите универсальную версию, которая должна работать с любым типом, который может хранить вектор:

template <typename T>
void only_distinct_duplicates(::std::vector<T> &v)
{
    ::std::sort(v.begin(), v.end());
    auto output = v.begin();
    auto test = v.begin();
    auto run_start = v.begin();
    auto const end = v.end();
    for (auto test = v.begin(); test != end; ++test) {
       if (*test != *run_start) {
           if ((test - run_start) > 1) {
              ::std::swap(*output, *run_start);
              ++output;
           }
           run_start = test;
       }
    }
    if ((end - run_start) > 1) {
        ::std::swap(*output, *run_start);
        ++output;
    }
    v.erase(output, end);
}

Answer 3

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

#include <algorithm>
#include <iostream>
#include <vector>

template<typename T>
void erase_unique_and_duplicates(std::vector<T>& v)
{
  auto first{v.begin()};
  std::sort(first, v.end());
  while (first != v.end()) {
    auto last{std::find_if(first, v.end(), [&](int i) { return i != *first; })};
    if (last - first > 1) {
      first = v.erase(first + 1, last);
    }
    else {
      first = v.erase(first);
    }
  }
}

int main(int argc, char** argv)
{
  std::vector<int> v{1, 2, 3, 4, 5, 2, 3, 4};
  erase_unique_and_duplicates(v);

  // The following will print '2 3 4'.
  for (int i : v) {
    std::cout << i << ' ';
  }
  std::cout << '\n';

  return 0;
}

Answer 4

В общем, эта задача имеет сложность с O (n * n), поэтому она выглядит медленной. Это должен быть вектор? Это ограничение? Должен ли он быть заказан? Если нет, то лучше на самом деле хранить значения как std::map, что исключает двойные числа при заполнении, или как std::multimap, если наличие двойных значений имеет значение.

Answer 5

Я позаимствую принципал из Python, который отлично подходит для таких операций -

Вы можете использовать словарь, где ключ-словарь - это элемент в векторе, а значение-словаря - это число (началос 1 и увеличивайте на единицу каждый раз, когда вы встречаете значение, которое уже есть в словаре).

впоследствии, создайте новый вектор (или очистите оригинал) только с ключами словаря, которые больше 1.

Посмотрите в google - std :: map

Надеюсь, это поможет.

Answer 6

У меня есть 2 улучшения для вас:

• Вы можете изменить count, чтобы начать с g1.begin() + i, все до этого обрабатывалось предыдущими итерациями цикла.

• Вы можете изменить if на == 2 вместо > 1, поэтому он будет добавлять числа только один раз, независимо от случаев. Если число в векторе 5 раз, первые 3 будут игнорироваться, 4-е превратится в новый вектор, а 5-е будет снова проигнорировано. Таким образом, вы можете удалить erase дубликатов

Пример:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    vector <int> g1 = {1,1,2,3,3,1,4};
    vector <int> g2;

    for(int i = 0; i < g1.size(); i++)
    {
      if(count(g1.begin() + i, g1.end(), g1[i]) == 2)
        g2.push_back(g1[i]);
    }

    for(int i = 0; i < g2.size(); i++)
    {
      cout << g2[i] << " ";
    }
    cout << endl;
    return 0;
}