Сформировать масcив и поместить него все неповторяющиеся числа

#cpp #массивы #динамические_массивы

Дан массив целых чисел X=(x1,x2,...,xn). Сформировать массив Y=(y1,y2,...,ym), поместив
в него в порядке убывания все различные (неповторяющиеся) числа, входящие в массив X.

Пытался вот так, но не корректно работает: 

void transferElements ()
{
    for (i = 0; i < size; i++)
    {
        f = 1;
        for (j = 0; j < size; j++)
        {
            if (X[i] == X[j])
            {
                f = 0;              
                break;
            }
            if (f == 1)
            Y[i] = X[i];
        }
    }
}

    

Ответы

Ответ 1

Huricane, в отличии от примера Timur Yalimov попробую решить задачу вообще без внешних
функций (типа qsort):

Основная логика в следующем:

Мы просматриваем все элементы и ищем каждый раз максимальное, но меньше максимального
на прошлом этапе поиска максимального

Таким образом - каждый этап мы будем находить одно уникальное число в порядке убывания

int transferElements(int* x, int x_size, int* y)
{
    int y_size = 0;

    int x_max = INT_MAX; // максимально возможное число int ~ +2.000.000.000

    for (int i = 0; i < x_size; i ++)
    {
        // определить максимальное число в массиве x, не превышающее x_max
        int x_local_max = INT_MIN; // минимально возможное число int ~ -2.000.000.000

        for (int j = 0; j < x_size; ++j)
        {
            if ((x[j] > x_local_max) && (x[j] < x_max))
                x_local_max = x[j];
        }

        // записать найденное число в выходной массив
        if (x_local_max > INT_MIN)
            y[y_size++] = x_local_max;

        // снизить границу максимальных чисел
        x_max = x_local_max;
    }

    return y_size;
}


Недостаток - алгоритм не оптимален и в массиве не должно быть числа MAX_INT (мы его
изначально как критерий используем)

От второго недостатка ты можешь избавиться уже сам

P.S.

а твой алгоритм не работает ну потому что он и не должен работать - например у тебя
только проверка на равно есть (а значит больше-меньше ты не определяешь) и запись только
в Y (а значит никак не воздействушь на X)

P.P.S.

чуть-чуть оптимальнее сделал - когда не находятся новые числа, не надо делать дальнейшие
проверки - можно прервать цикл

int transferElements(int* x, int x_size, int* y)
{
    int y_size = 0;

    int x_max = INT_MAX; // максимально возможное число int ~ +2.000.000.000

    for (int i = 0; i < x_size; i ++)
    {
        // определить максимальное число в массиве x, не превышающее x_max
        int x_local_max = INT_MIN; // минимально возможное число int ~ -2.000.000.000

        for (int j = 0; j < x_size; ++j)
        {
            if ((x[j] > x_local_max) && (x[j] < x_max))
                x_local_max = x[j];
        }

        // завершить обработку, если новых чисел не найдено
        if (x_local_max <= INT_MIN)
            break;

        // записать найденное число в выходной массив
        y[y_size++] = x_local_max;

        // снизить границу максимальных чисел
        x_max = x_local_max;
    }

    return y_size;
}


Ответ 2

Попробуйте так:

#include 
#include 

#define SIZE (7)

int compare(const void * x1, const void * x2)   

{
   return ( *(int*)x2 - *(int*)x1 );            
}

int Task(int * arr, int * res)

{
    qsort(arr, SIZE, sizeof(int), compare);

    int res_cnt = 0;

    for (int i = 0; i < SIZE; i++)

    {
       if ((arr[i] != arr[i + 1] && arr[i] != arr[i] - 1 && i != 0) || (i == 0)) 

        {
           res[res_cnt++] = arr[i];
        }  
    }

    return res_cnt;
}


int main()

{

    int array[SIZE]  = { 1, 0, 50, 50, 20, 20, 300 };
    int result[SIZE] = { 0 };
    int result_size = Task(array, result);
}


Здесь в result_size будет храниться размер получившегося массива, если вам разрешено
- можете по нему выделять динамическую память.


Ответ 3

Способ №1 (доводим ваш пример кода до рабочего состояния):

using value_type = int;

int CompFunc(const void * a, const void * b)
{
    if ( *static_cast(a) > *static_cast(b) )
        return -1;
    else
        if ( *static_cast(a) < *static_cast(b))
            return 1;
        else
            return 0;
}

size_t TransferElement(value_type *x, size_t size, value_type *y)
{
    if ( size == 0 )
        return 0;

    size_t ySize = 0;
    bool flag;

    for ( size_t i = 0; i != size; ++i )
    {
        flag = true;
        for ( size_t j = 0; j != ySize; ++j )
            if ( x[i] == y[j] )
            {
                flag = false;
                break;
            }
        if ( flag )
        {
            y[ySize] = x[i];
            ++ySize;
        }
    }
    qsort(y, ySize, sizeof(value_type), CompFunc);
    return ySize;
}




Способ №2 (Немного оптимизируем ваш алгоритм):

size_t TransferElements(value_type *x, size_t size, value_type *y)
{
    if ( size == 0 )
        return 0;

    for ( size_t i = 0; i != size; ++i )
        y[i] = x[i];
    qsort(y, size, sizeof(value_type), CompFunc);

    value_type controlVal = y[0];
    size_t ySize = 1;

    for ( i = 1; i != size; ++i )
        if ( controlVal != y[i] )
        {
            controlVal = y[i];
            y[ySize] = controlVal;
            ++ySize;
        }
    return ySize;
}


Сложность первого способа O(N^2), сложность второго O(N) (без учёта сортировки).
Однако второй способ требует, чтобы размер массива y был таким же как и x.



Способ №3 (по мотивам комментария @Harry):

typedef vector vect_type;
vect_type x, y;
//...
y = x;
sort(y.begin(), y.end(), greater());
auto last = unique(y.begin(), y.end());
y.erase(last, y.end());