Дан одномерный массив целых чисел. Вставить число k перед всеми элементами, в которых есть цифра 1. Нужно осуществить с помощью сдвига вправо

Question

Не могу найти ошибку в коде, вывод массива при изменении не корректный.

static void Main(string[] args)
{
    Console.WriteLine("Введите размерность массива");
    int n = Convert.ToInt32(Console.ReadLine());
    int[] m = new int[n * 2];
    int k = 0;
    Random r = new Random();
    Console.WriteLine("Начальный массив");

    for (int i = 0; i < n; i++)
    {
        m[i] = r.Next(-100, 100);
        Console.Write("{0,5}", m[i]);
    }
    Console.WriteLine();

    int a = 0;
    int count = 0;
    for (int i = 0; i < n; i++)  
    {
        int d = 0;
        a = Math.Abs(m[i]);
        while (a > 0)
        {
            if (a % 10 == 1)
            {
                d = 1;
            }
            a /= 10;
        }
        if (d == 1)
        {
            count++;

            for (int p = n + count - 1; p > i + count - 1; p--)
            {
                m[p] = m[p - 1];
            }

            m[i + count - 1] = k;
            i++;

        }
    }

    Console.WriteLine("Измененный массив");
    for (int i = 0; i < n + count; i++)
    {
        Console.Write("{0,5}", m[i]);
    }
    Console.WriteLine();
}

Answer 1

Попробуйте такой вариант основного цикла:

for (int i = 0; i < n; i++)
{
    if ($"{m[i]}".Contains("1"))
    {
        n++;

        for (int p = n - 1; p >= i; p--)
        {
            m[p] = m[p - 1];
        }

        m[i] = k;
        i++;
    }
}

ну и вывод измененного массива тоже

Console.WriteLine("Измененный массив");
for (int i = 0; i < n; i++)
{
    Console.Write("{0,5}", m[i]);
}

Answer 2

Код из вопроса и из ранее приведенного ответа не совсем оптимален, выполняется за время O(n^2) в худшем случае.

Можно сделать за время O(n), если сначала выяснить, сколько всего надо вставить чисел, и потом в цикле смещать элементы на требуемое расстояние:

int count = 0;
for (int i = 0; i < n; ++i)  
{
    count += HasOne(m[i]) ? 1 : 0;
}

for (int c = count, i = n - 1; i >= 0; --i) {
    m[i + c] = m[i];

    if (HasOne(m[i])) {
        --c;
        m[i + c] = k;
    }
}

БЛОГ НА HUSL

Дан одномерный массив целых чисел. Вставить число k перед всеми элементами, в которых есть цифра 1. Нужно осуществить с помощью сдвига вправо

Ответы (2 шт):