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

184
10 декабря 2017, 12:01

Дан массив целых чисел 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];
        }
    }
}
Answer 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;
}
Answer 2

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

#include <iostream>
#include <cstdlib>
#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 будет храниться размер получившегося массива, если вам разрешено - можете по нему выделять динамическую память.

Answer 3

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

using value_type = int;
int CompFunc(const void * a, const void * b)
{
    if ( *static_cast<const value_type *>(a) > *static_cast<const value_type *>(b) )
        return -1;
    else
        if ( *static_cast<const value_type *>(a) < *static_cast<const value_type *>(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<int> vect_type;
vect_type x, y;
//...
y = x;
sort(y.begin(), y.end(), greater<vect_type::value_type>());
auto last = unique(y.begin(), y.end());
y.erase(last, y.end());
READ ALSO
Почему minGW компилятор не открывает Handle файл?

Почему minGW компилятор не открывает Handle файл?

создаю Handle hfileИспользую FindFirstFile,и проверяю с hFile!=INVALID_HANDLE_VALUE

202
Как добавить свой виджет на главное окно Qt

Как добавить свой виджет на главное окно Qt

Создал свой виджет для визуализации круговой диаграммы:

257
Перегрузка оператора -&gt;

Перегрузка оператора ->

Как то не логично работает вызов под номером 1, теряется уровень косвенности, ведь возвращается указатель, почему к нему сразу можно применить...

180
Замена с помощью regexp

Замена с помощью regexp

Простое задание: заменить дату в формате "ддмм

172