БлогNot. C++: удалить из целочисленного массива повторяющиеся элементы

Помощь дата->рейтинг Поиск Почта RSS канал Статистика nickolay.info Домой

C++: удалить из целочисленного массива повторяющиеся элементы

Если нужен не готовый метод array_unique, как в PHP, а "ручная" реализация, то проще всего выглядит примерно такой код, имеющий вычислительную сложность порядка O(N2), проверено в Studio:

#include <stdio.h>
#include <stdlib.h>

size_t remove_duplicate_items(int *arr, size_t len) {
 size_t prev = 0;
 size_t curr = 1;
 size_t last = len - 1;
 while (curr <= last) {
  for (prev = 0; prev < curr && arr[curr] != arr[prev]; ++prev);
  if (prev == curr) ++curr;
  else {
   arr[curr] = arr[last];
   --last;
  }
 }
 return curr;
}

void print_array(int *arr, size_t len) {
 printf("{");
 size_t curr = 0;
 for (curr = 0; curr < len; ++curr) {
  if (curr > 0) printf(", ");
  printf("%d", arr[curr]);
 }
 printf("}");
}

int main() {
 int arr[] = { 1,1,1,2,4,-3,5,2,3,4 };
 printf("Before: ");
 size_t len = sizeof (arr) / sizeof (arr[0]);
  //так легко узнать размерность массива
 print_array(arr, len);
 len = remove_duplicate_items(arr, len);
 printf("\nAfter: ");
 print_array(arr, len);
 getchar();
 return 0;
}

Есть ещё старое алгоритмическое решение на Паскале вот тут.

Если требуется решить задачу "современненько", с векторами и итераторами, но без наглядного представления и понимания сути алгоритма, то тогда так:

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int removeDuplicateItems (vector<int>& numbers) {
 set <int> seenNums;
 auto itr = begin(numbers);
 while(itr != end(numbers)) {
  if (seenNums.find(*itr) != end(seenNums)) itr = numbers.erase(itr);
  else {
   seenNums.insert(*itr);
   itr++;
  }
 }
 return seenNums.size();
}

void print_vector (const vector <int> &v){
 for (size_t i=0; i<v.size(); i++) cout << v[i] << " ";
}

int main() {
 static const int a[] = { 1,1,1,2,4,-3,5,2,3,4 };
 vector <int> arr (a, a + sizeof(a) / sizeof(a[0]) );
  //инициализироавать vector списком инициализации "напрямую"
  //можно только в новом стандарте C++11
 cout << "Before: ";
 print_vector(arr);
 int len = removeDuplicateItems (arr);
 cout << "\nAfter: ";
 print_vector(arr);
 cin.get();
 return 0;
}

теги: c++ алгоритм

01.03.2017, 23:04; рейтинг: 2004

  свежие записипоиск по блогукомментариистатистикао "вирусах" в архивах .zip

Наверх Яндекс.Метрика
© PerS
вход