Как изменить положение элементов массива C ++ в зависимости от заданных условий?

Question

У меня возникла небольшая проблема с тем, чтобы свести голову с этим домашним заданием. Задача гласит:

"Напишите функцию с именем MoveSmallest , которая перемещает все минимальные целочисленные элементы в начале массива. Все остальные элементы должны оставаться на своих местах. (Массив и его размер параметры)

Пример: массив: 2, 3, 5, 1, 2, 3, 6, 4, 2, 1, 1 изменяется на 1, 1, 1, 2, 3, 5, 2 , 3, 6, 4, 2

void MoveSmallest(int A[],int n)
{
int Min;
for(int i=0;i<n;i++)
{
    if(i==0)
    {
        Min=A[i];
    }
    else if(A[i]<=Min)
    {
        Min=A[i];
    }
}

Пока что я только решил проверить, какой из них является наименьшим элементом массива. У меня нет идей, что делать дальше.

Answer 1

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

Вы можете сделать это, переставляя значения до тех пор, пока вы не окажетесь «слева» от массива (т. Е. Индекс 0).

void MoveSmallest(int A[],int n)
{
    int Min;
    for(int i=0;i<n;i++)
    {
        if(i==0)
        {
            Min=A[i];
        }
        else if(A[i]<=Min)
        {
            Min=A[i];
        }
    }

    for(int i = 0; i < n; i++)
    {
        if(A[i] == Min)
        {
            for(int j = i; j > 0; j--)
            {
                int tmp = A[j];
                A[j] = A[j-1];
                A[j-1] = tmp;
            }
        }
    }
}

Вы также можете использовать std::swap для выполнения перестановки вместо временной переменной tmp.

Answer 2

Поскольку в ваших сообщениях упоминается «базовый C ++», но не упоминается «базовый», вот еще одно решение. При этом предполагается, что создание массивов для «рабочих» целей считается «базовым C ++».

void MoveSmallest(int A[], int n)
{
    // get the minimum value
    int Min = A[0];
    for (int i = 1; i < n; ++i)
    {
        if (A[i] < Min)
            Min = A[i];
    }

    // get the count of the number of minimum values
    int minCount = 0;
    for (int i = 0; i < n; ++i)
    {
        if (A[i] == Min)
            ++minCount;
    }

    if (minCount > 0)
    {
        // create a work array and fill in the first
        // minCount values with the minimum value
        int *B = new int[n];
        for (int i = 0; i < minCount; ++i)
            B[i] = Min;

        // now fill in the rest of the work array with the values
        // in the A[] array that are not equal to Min
        int current_pos = minCount;
        for (int i = 0; i < n; ++i)
        {
            if (A[i] != Min)
                B[current_pos++] = A[i];
        }

        // Now copy work array back to A array  
        for (int i = 0; i < n; ++i)
            A[i] = B[i];

        // get rid of work array
        delete[] B;
    }
}

Живой пример

Это выполняется за линейное время O(n), в отличие от квадратичного времени O(n*n).

Недостатком, конечно, является то, что вам нужно место для рабочего массива, поэтому стоимость памяти линейна O(n).

Answer 3

Начиная с конца массива, отслеживайте, сколько минимальных элементов вы встретили. Затем всякий раз, когда вы сталкиваетесь с не минимальным элементом, перемещайте его вправо на количество минимальных элементов, с которыми вы уже столкнулись:

void MoveSmallest(int A[], int n)
{
    int min;

    //Find min logic

    //shift non-min elements and count min elements
    int cnt = 0;
    for (int i = n-1; i >=0; --i)
    {
        if (A[i] == min)
            cnt++;
        else
            A[i+cnt] = A[i];
    }

    //Add min elements
    for (int i = 0; i < cnt; ++i)
        A[i] = min;

}

Это будет выполняться за время O (n) и пространство O (1).