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 that you have read and understand our privacy policy and code of conduct.

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