Дан массив целых чисел 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];
}
}
}
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;
}
Попробуйте так:
#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 будет храниться размер получившегося массива, если вам разрешено - можете по нему выделять динамическую память.
Способ №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());
Виртуальный выделенный сервер (VDS) становится отличным выбором
создаю Handle hfileИспользую FindFirstFile,и проверяю с hFile!=INVALID_HANDLE_VALUE
Создал свой виджет для визуализации круговой диаграммы:
Как то не логично работает вызов под номером 1, теряется уровень косвенности, ведь возвращается указатель, почему к нему сразу можно применить...