Оптимизация и рефакторинг алгоритма

Question

Дан массив чисел. Нужно его сдвинуть циклически на K позиций влево, не используя других массивов. Сделал для неубывающего массива. Есть ли универсальный способ

    public static int[] DoShift(int[] arrayToShift, int countOfShifts)
    {

        countOfShifts %= arrayToShift.Length;
        for (int i = countOfShifts; i < arrayToShift.Length; i++)
        {
            (arrayToShift[i], arrayToShift[i - countOfShifts]) = (arrayToShift[i - countOfShifts], arrayToShift[i]);
        }
        
        for (int i = arrayToShift.Length - countOfShifts; i < arrayToShift.Length - 1; i++)
        {
            for (int j = i + 1; j < arrayToShift.Length; j++)
            {
                if (arrayToShift[i] > arrayToShift[j])
                {
                    (arrayToShift[i], arrayToShift[j]) = (arrayToShift[j], arrayToShift[i]);
                }
            }
        }

        return arrayToShift;
    }

Answer 1

Для сдвига на 1 позицию влево можно использовать простой алгоритм - запомнить первый элемент, сдвинуть все остальные, поставить запомненный на последнее место. Для сдвига на небольшое K можно использовать это же K раз, что приводит к сложности O(KN), но в общем случае есть чудесный линейный алгоритм O(N):

Перевернуть подмассив из первых K элементов (производится на месте)
Перевернуть подмассив из последних N-K элементов
Перевернуть весь массив

3 8 1 2 4 7  K=3
1 8 3  2 4 7
1 8 3  7 4 2
2 4 7 3 8 1

БЛОГ НА HUSL

Оптимизация и рефакторинг алгоритма

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