Обнуление значений в массиве

Question

Обнуление значений в массиве

Рейтинг: 0Ответов: 2Опубликовано: 13.05.2023

Мне было дано задание: сделать так, чтобы после ввода массива А все его элементы меньше или равные 1 были удалены, а освободившиеся места заполнились в конце и нолями (т.е. преобразование {2, 45, 1, 3} в {2, 45, 3, 0}, {0, 9, 4, 1, 8} в {9, 4, 8, 0, 0} и т.д.). Запрещено менять порядок (не считая сдвига из примера) и использовать другие массивы.

Решение пока что сырое (не прикрутил ввод массива и не учёл вариант, где два элемента меньше или равные 1 встречаются подряд):

#include <array>
using namespace std;

int main()
{
    int deleteNum = 0;
    int A [6] {1, 5, 4, 3, 9, 4}; //случайные цифры, для проверок я периодически их меняю
    int longA = end(A)-begin(A);
    for(int i = 0; i < longA; i++) {
        if (A[i] <= 1) {
            for (int u = i; u < (longA - deleteNum); u++) {
                A[u] = A[u + 1];
            }
            A[longA - 1 - deleteNum] = 0;
            deleteNum += 1;
        }
    }
    cout << A[0] << A[1] << A[2] << A[3] << A[4] << A[5];

    return 0;
}

Во время проверки я обнаружил странную вещь. Практически при любом положении 1 в массиве, на выводе появляется лишний ноль, а то и несколько:

{9, 6, 4, 7, 1, 9} => {9, 6, 4, 7, 0, 0}

{1, 6, 4, 1, 8, 9} => {6, 4, 0, 0, 0, 0}

Подскажите, пожалуйста, что я делаю не так (а если кто посоветует, как решить вариант с двумя и более идущими подряд единицами, то ему отдельное спасибо).

c# массивы

Источник: Stack Overflow на русском

Answer 1

▲ 3Принят

А зачем так сложно? Ведь если единиц и меньше будет много, получится O(n²)...

Не хотите такой вариант?

int A [6] {2, 5, 7, 3, 9, 4}; //случайные цифры, для проверок я периодически их меняю
int d = 0;
for(int s = 0; s < size(A); ++s)
{
    if (A[s] <= 1) continue;
    A[d++] = A[s];
}
for(;d < size(A); ++d) A[d] = 0;

cout << A[0] << A[1] << A[2] << A[3] << A[4] << A[5];

Answer 2

▲ 1

Цикл обрабатывает нули в конце массива ещё раз и стирает в два раза больше элементов чем нужно. Поправить можно так:

<     for(int i = 0; i < longA; i++) {
---
>     for(int i = 0; i < longA - deleteNum; i++) {

Для удаления неугодных элементов в С++ есть remove_if. Он перемещает угодные элементы в начало массива, в хвосте остаётся мусор, который надо заполнить нулями (fill):

#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    int a[] {1, 5, 4, 3, 9, 4};
    fill(
        remove_if(begin(a), end(a), [](auto v) { return v <= 1; }),
        end(a),
        0
    );
    for (auto v : a) {
        cout << ' ' << v;
    }
    cout << '\n';
}

Если интересно, как устроен remove_if изнутри, код есть по ссылке выше. Алгоритм использует два индекса i, j и копирует хорошие элементы из i в j. Плохие элементы пропускаются. По окончании цикла все хорошие элементы в начале массива в диапазоне [0, j):

#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    int a[] {1, 5, 4, 3, 9, 4};
    const int n = size(a);

    int j = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i] > 1) {
            a[j] = a[i];
            ++j;
        }
    }
    for (; j < n; ++j) {
        a[j] = 0;
    }

    for (auto v : a) {
        cout << ' ' << v;
    }
    cout << '\n';
}

remove_if работает быстрее чем ваш код. Вы копируете элементы из хвоста многократно, remove_if копирует каждый элемент только один раз. В терминах сложности ваш код квадратичный, код remove_if линейный. Разница будет заметна с ростом длины массива, если в массиве много неугодных элементов.

Обнуление значений в массиве

Ответы