0

Из массива А[length], записать в массив B[length] только числа которые повторяются в A[length] один раз и вывести на экран. Не могу допереть, как это реализовать. Ниже начал написал заполнение первого массива, но со вторым траблы.

int const length = 20;
int arr1[length];
cout << "Исходный массив: \n";
for (int i = 0; i < length; i++) {
    arr1[i] = -20 + rand() % 41;
    cout << arr1[i] << " ";
}
cout << "\n\n";

cout << "Результирующий массив: \n";
int arr_1[length];

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

    for (int j = i+1; j < length; j++)
    {
        if (arr1[i] == arr1[j]){
            break;
        }
        else{
            arr_1[i] = arr1[i];
        }
    }
    cout << arr_1[i] << " ";
}
8
  • попробуйте выполнить ваш код по строчкам, тогда вы поймёте, что программа делает что-то не то в цикле. Только сделайте число элементов поменьше, чтобы было проще. И вместо k=false логичнее просто выходить из цикла, он всё равно пользы больше не принесёт
    – Eikthyrnir
    18 сен 2019 в 16:19
  • если Вы знаете в чем проблема, пожалуйста скажите, я еще начинающий могу не понять. Я конкретно НЕ знаю как выполнить эту задачу. 18 сен 2019 в 16:22
  • вы всё делаете правильно, просто нужно научиться кропотливо искать проблему, это часто придётся делать, если собираетесь программировать) я могу вам расписать на что обратить внимание при поиске ошибок, за вас я писать не буду, уж простите
    – Eikthyrnir
    18 сен 2019 в 16:23
  • Но первый элемент все равно нужно записать же? 18 сен 2019 в 16:37
  • С чего вы взяли, вдркг весь arr1 состоит из одних и тех же чисел
    – Eikthyrnir
    18 сен 2019 в 16:41

2 ответа 2

3

Начнём решать "в лоб". По сути просто исправим ваш код, но я всё же прокомментирую основные моменты данного решения. Итак, мы про ходим по всем элементам массива А, и, если элемент уникальный(для проверки снова пробегаемся по массиву А в поисках такого же), записываем в массив В. Получаем сложность O(n^2), где n-количество элементов в A.

#include <iostream>
using namespace std;

int main() 
{
    int const length = 20;
    int A[length];
    cout << "Исходный массив: \n";
    for (int i = 0; i < length; i++)
    {
        A[i] = -20 + rand() % 41;
        cout << A[i] << " ";
    }
    cout << "\n\n";

    int B[length];
    int B_logical_length = 0;

    for (int i = 0; i < length; i++)
    {
        //проверка на уникальность
        //тут я в комментариях наговорил ерунды, и пробегать надо всё таки весь массив А
        bool unique = true;
        for (int j = 0; j < length; j++)
        {
            if (A[j] == A[i] && j != i)
            {
                unique = false;
                break;
            }
        }

        if (unique)
        {
            B[B_logical_length] = A[i];
            ++B_logical_length;
        }
    }

    cout << "Результирующий массив: \n";
    for (int i = 0; i < B_logical_length; i++)
    {
        cout << B[i] << " ";
    }

    return 0;
}

Всё это отлично работает при сравнительно небольших объемах данных. Если же у нас довольно большой массив, из-за высокой сложности предыдущий алгоритм может работать довольно медленно.

Попытаемся слегка его усовершенствовать.

Довольно очевидно, что нам в любом случае придётся перебирать все элементы из А(обозначим этот процесс за (1)), это как минимум n действий. Следовательно следует уменьшить время затрачиваемое на проверку уникальности элемента. Этого можно добиться предварительно отсортировав элементы А. Способов сортировки множество, нас интересуют те, временная сложность которых лучше O(n^2). Преимущество отсортированых данных можно увидеть на следующем примере. Пусть у нас есть некоторый набор чисел и после сортировки он выглядит следующим образом: 1, 2, 2, 3, 4, 7, 7, 7, 8, 9, 9. Видно, что, чтобы проверить элемент на уникальность, достаточно рассмотреть следующий элемент, что мы можем вполне можем сделать в процессе перебора массива А.

В результате получаем сложность приблизительно равную сложности выбранного алгоритма сортировки

n.b. Можете попытаться реализовать 2ой алгоритм для тренировки

6
  • 1
    Если говорить об эффективности, то стоит упомянуть возможность использования доп структур (хеша или дерева)...
    – Fat-Zer
    18 сен 2019 в 19:59
  • @Fat-Zer наверное вы правы, но я хотел лишь показать как можно улучшить интуитивный(1ый) алгоритм. Я в это время как-то даже не думал про другие структуры данных, ибо в вопросе написано про массив. И я кстати не уверен, что в конечном итоге какое-нибудь дерево или хэштаблица покажут лучшую эффективность по времени
    – Eikthyrnir
    18 сен 2019 в 20:04
  • по эффективности, хеш будет асимптотически работать за O(N)... дерево — всегда за O(N*log(U)), где U— количество уникальных элементов... но OP'у это конечно всё ещё рано учить, впрочем как и то, что такое какой-нить qsort, так что я упомянул только для справки...
    – Fat-Zer
    18 сен 2019 в 20:16
  • @Fat-Zer да, в среднем хэш и правда будет работать быстрее, я затупил. Если вы не против я воспользуюсь вашей идеей и дополню ответ, или, что лучше, сделайте это сами
    – Eikthyrnir
    18 сен 2019 в 20:32
  • конечно не против ;)... сам я не соберусь в ближайшее время...
    – Fat-Zer
    18 сен 2019 в 20:46
0

Если можно пользоваться библиотекой С++, то

int const length = 20;
int arr1[length];

cout << "Исходный массив: \n";
for (int i = 0; i < length; i++) {
    arr1[i] = -20 + rand() % 41;
    cout << arr1[i] << " ";
}
cout << "\n\n";

cout << "Результирующий массив: \n";

sort(arr1,arr1+length);
int * end = unique(arr1,arr1+length);

for (int i = 0; i < end - arr1; i++) {
    cout << arr1[i] << " ";
}
cout << "\n\n";

В вашем массиве первые end - arr1 элементов теперь уникальны. Можно их перекопировать, куда надо.

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

1
  • Нет, библиотекой я пока не могу и не умею пользоваться. В том то и дело. 18 сен 2019 в 15:48

Ваш ответ

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

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