2

есть массив massC в котором необходимо удалить повторяющиеся элементы ну и потом их сумму узнаьб на главное что меня интересует как удалить повторяющиеся

#include <iostream>
#include <time.h>
using namespace std;

void main()
{
    const int size = 15, sum = 1;
    int massA[size], massB[size];
    int massC[sum] = { 0 };
    srand(time(NULL));
    for (int i = 0; i < size; i++)
    {
        massA[i] = rand() % 100 -50;
        cout << massA[i] << " ";
    }
    cout << endl;
    for (int i = 0; i < size; i++)
    {
        massB[i] = rand() % 100 - 50;
        cout << massB[i] << " ";
    }
    int k = 0;
    cout << endl;
    for (int i = 0; i < size; i++)
    {
        bool buf = false;
        for (int j = 0; j < size; j++)
        {
            if (massA[i] == massB[j]) {
                buf = true; break;
            }
        }
        if (!buf) {
            if (massA[i] < 0) {
                massC[k] = massA[i];
                cout << massC[k] << " ";
                k++;

            }
        }
    }
    cout << endl;
}
9
  • Sort + unique сложность n logn .
    – pavel
    25 июл 2016 в 18:44
  • @tkachuk, (1) из статического массива невозможно удалять элементы их можно только поменять местами, (2) какой принцип отбора?
    – perfect
    25 июл 2016 в 18:53
  • 3
    А можно hash_set использовать и за O(n)...
    – pavel
    25 июл 2016 в 18:58
  • @perfect принцип отбора? не совсем понимаю о чем речь идет
    – tkachuk
    25 июл 2016 в 19:08
  • 1. нужно ли сохранить порядок элементов? 2. нужно ли удалить и повторяющиеся значения и первое такое же значение? 3. сумму кого "их" нужно получить?
    – Max T
    25 июл 2016 в 19:28

4 ответа 4

10

Контейнер std::unordered_set (C++11) помогает эффективно решать подобный задачки.

// g++ -std=c++11 ...
#include <iostream>
#include <unordered_set>

using namespace std;

int main ()
{
  int a[] = { 2, 5, 2, 4, 4, 7 };
  int n = 0; // здесь будет количество уникальных элементов a[]
  long long sum = 0;
  unordered_set<int> s;

  cout << "исходный массив:\n";
  for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++) {
    cout << a[i] << ' ';

    if (s.insert(a[i]).second) { // попытаемся добавить в множество
      // такого еще не было
      sum += a[i];    // скорректируем сумму различных элементов
      // передвинем новый уникальный элемент на нужное место
      a[n++] = a[i];  
    }
  }

  cout << "\nсумма различных элементов a[]: " << sum 
       << "\nтеперь в a[] осталось различных элементов: " << n << '\n';
  for (int i = 0; i < n; i++)
    cout << a[i] << ' ';
  cout << '\n';
}

А уникальные элементы можно просто перемещать к началу, в том же массиве, затирая те элементы, которые уже встречались.

Update
Думаю, после комментариев и правки ответа рядом участников,
(первоначально код содержал if (s.find(a[i]) == s.end()) { ... т.е. явно проводилась проверка наличия данных в множестве s)
имеет смысл подробнее посмотреть на функцию insert(), которая либо вставляет новый элемент в множество, либо сообщает о том, что такое значение в нем уже есть.

Эта функция возвращает вот такую пару значений:

pair<unordered_set<int>::const_iterator, bool> p = s.insert(a[i]);

Первый член пары указывает на элемент в множестве, а второй сообщает был ли элемент только что добавлен (true) или уже существовал (false).

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

Кстати, возможно кому-нибудь окажется полезным простейший код (без сторонних библиотек, Си и C++), реализующий множество целых ограниченного размера, который позволяет только добавлять новые элементы.

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

struct siset {
  int size;
  int data[];
};

#define BITSIZE(T) (sizeof(T) * CHAR_BIT)

static inline int testbit (int b[], int n) {
  return b[n / BITSIZE(b[0])] & (1 << (n % BITSIZE(b[0])));
}

static inline  void setbit (int b[], int n) {
  b[n / BITSIZE(b[0])] |= (1 << (n % BITSIZE(b[0])));
}

struct siset *
make_siset (int size)
{
  int sz = size + size / 2 + 1, 
    bsz = sz / BITSIZE(int) + ((sz & (BITSIZE(int) - 1)) != 0);
  struct siset *s = (__typeof__(s))malloc(sz + 1 + bsz);
  s->size = sz;

  bzero(s->data + bsz, bsz * sizeof(s->data[0]));
  return s;
}

int
siset_insert (struct siset *set, int v)
{
  int n = 0, // sentinel
    j = (unsigned)v % set->size;

  for (; testbit(set->data + set->size, j) && n < set->size; 
       j = (j + 1) % set->size, n++)
    if (set->data[j] == v)
      return 0;
  if (n < set->size) {
    setbit(set->data + set->size, j);
    set->data[j] = v;
    return 1;
  }
  // table overflow
  return 0;
}

int
siset_find (struct siset *set, int v)
{
  int n = 0, // sentinel
    j = (unsigned)v % set->size;

  for (; testbit(set->data + set->size, j) && n < set->size; 
       j = (j + 1) % set->size, n++)
    if (set->data[j] == v)
      return 1;

  return 0;
}
13
  • без всяких библиотек нужно. своими силами
    – tkachuk
    25 июл 2016 в 19:53
  • @avp здравствуйте , вот так, интернет всю культуру людей изменил, своими силами это теперь значит чтобы другие люди в сети это вместо тебя это сделали ))
    – perfect
    25 июл 2016 в 20:14
  • Примитивная хеш таблица пишется минут за 5, обычно хвтатает.
    – pavel
    25 июл 2016 в 20:31
  • По коду, не надо делать поиск, insert вернет значение была вставка или нет.
    – pavel
    25 июл 2016 в 20:32
  • 3
    @pavel: В учебных целях — да, но написать самому, а не спросить на StackOverflow.
    – VladD
    25 июл 2016 в 20:43
3

massA - исходные массив с повторяющимися значениями massB - результирующий массив без повторений massC - (в моём коде) временный рабочий массив

#include <iostream>
#include <time.h>
using namespace std;

void main()
{
const int size = 15; // размер исходного массива
const int max = 10;  // максимальное значение элемента массива
int i;
int massA[size], massB[size], massC[max];
srand(time(NULL));
// заполнить массив тестовыми значениями
for (i = 0; i < size; i++)
{
    massA[i] = rand() % max;
    cout << massA[i] << " ";
}
cout << endl;
// обнулить рабочий временный массив
for (i = 0; i < max; i++)
    massC[i] = 0;

int j = 0;
for (i = 0; i < size; i++)
{
    if (!massC[massA[i]]) // если значение уникально..
    {
        massB[j++] = massA[i]; //..то сохранить его в результирующем
        massC[massA[i]] = 1;   // пометить значение как использованное
    }
}


for (i = 0; i < j; i++)
{
    cout << massB[i] << " ";
}
cout << endl;

getchar();
}
3

Если я правильно понял вопрос то можно так сделать:

#include <iostream>

using namespace std;

int main()
{
    int arr[5] = { 2, 5, 2, 4, 4};
    int result = 0;
    int temp;

    // Расставляем элементы массива по порядку '2, 2, 4, 4, 5'
    // Можно реализовать по-другому 

    for (int i = 0; i < 5 - 1; i++)
        for (int j = 0; j < 5 - i - 1; j++)
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }

    temp = 0;

    for (int i = 0; i < 5; i++) { 

        // Если элемент в temp равен текущему элементу(они повторяются) то текущий элемент заменяется на 0
        // примерно так [ 2 - temp, 2 - текущий элемент, 4, 4] текущий элемент будет равен 0
        // Иначе прибавляем к результату(сумма массива) текущий элемент и кладем его в temp

        if (temp == arr[i]) arr[i] = 0; 
        else {
            result += arr[i];
            temp = arr[i];
        }
    }
    cout << result << endl;
    return 0;
}

Значения в массиве сортируются и потом сравниваются. Если предыдущий элементы равен текущему то текущий заменяется на 0.

// Действительно была ошибка. Сразу не углядел за скобками. Теперь все работает.

7
  • Визуально ошибка если вы введете более 2 одинаковых элементов. Да и лучше стандартный метод вызвать хотя бы для сортировки...
    – pavel
    25 июл 2016 в 18:54
  • Действительно была ошибка. Сразу не углядел за скобками. Теперь все работает.
    – Brik Vadim
    25 июл 2016 в 19:00
  • @BrikVadim а можно с комментариями там где начинается for (int j = 0; j < 5 - i - 1; j++) а то не совсем понимаю
    – tkachuk
    25 июл 2016 в 19:28
  • @tkachuk сортировка пузьком, думаю её все среди ночи узнают. Если сразу не узнается то дальше ещё сложнее для восприятия.
    – pavel
    25 июл 2016 в 20:42
  • @pavel сортировку еще не учил
    – tkachuk
    26 июл 2016 в 8:56
0

От делать нечего написал решение без стандартной библиотеки.

#include <iostream>

using namespace std;

const int SIZE = 9; // размер массива

// ф-я вывода
void print(const int * arr, const size_t size = SIZE){
    for (size_t i = 0; i < size; i++)
        cout << "[" << arr[i] << "]";
     cout << endl;
}

// ф-я ищет дубликаты в массивы с позиции (current_posizito)
bool isNextExist(const int * arr, const size_t current_posiziton, const int find_number){
    for (size_t i = current_posiziton + 1; i < SIZE; i++)
        if (arr[i] == find_number)
            return true;

    return false;
}

// ф-я перемещает элемент с указанной позиции в конец массива
void moveInEnd(int * arr, const size_t position){
    int tmp = arr[position];

    for (size_t i = position; i < SIZE; i++)
        arr[i] = arr[i + 1];

    arr[SIZE - 1] = tmp;
}

// ф-я помещает уникальные элементы в начале массива и возвращает их количество
const size_t unique(int * arr){
    size_t len = SIZE;

    for (size_t i = 0; i < len; i++){
        if (isNextExist(arr, i, arr[i])){
            moveInEnd(arr, i);

            //print(arr); // раскоментировать для отладки

            len--;
            i = 0;

            continue;
        }
    }

    return len;
}

int main(){
    int arr[SIZE] = { 9, 2, 2, 3, 4, 4, 2, 2, 8 };
    size_t len;

    cout << "source array:" << endl;
    print(arr);

    len = unique(arr);

    cout << endl << "array after unique processing: " << endl;
    print(arr);

    cout << endl << "Unique elements " << len << ", here they are ";
    print(arr, len);


    return 0;
}

вывод:

результат

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.