JavaМоим ученикам

Циклический сдвиг в одномерном массиве

No votes yet.
Please wait...

Не так давно стартовал очередной курс Java на одном небезызвестном образовательном портале. И вот, моим студентам досталась задача по работе с массивами. Статья в первую очередь для них, но и для интересующихся, конечно же 🙂

Итак, задача сформулирована следующим образом

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

Разумеется, после первых подходов к алгоритмизации данной задачи многие студенты нашли следующее довольно логичное и вполне корректное решение. Оно весьма популярно на различных сайтах, описывающих циклический сдвиг. Суть его в том, что любой сдвиг можно представить в качестве n сдвигов на 1 ячейку. Сдвиг на 1 ячейку довольно просто реализуется циклом. В итоге, если изобразить это Java-методом, получается примерно такой метод:

public static int[] shiftArray(int[] incomingArray, int shift) {
    if(shift != 0){
        // Любой сдвиг больше длины массива можно оптимизировать до меньшего сдвига
        // через деление по модулю
        int finalShift
        if (shift > incomingArray.length)
            shift = Math.abs(shift % incomingArray.length);
        else
            finalShift = shift;
        // в зависимости от знака сдвига движение будет происходить
        // слева направо при положительном сдвиге
        // справа налево при отрицательном
        if (shift > 0) {
            for (int n = 0; n < shift; n++) {
                // убираем первый элемент в буфер, а на его место ставим хвостовой элемент
                int buffer = incomingArray[0];
                myArray[0] = incomingArray[incomingArray.length - 1];
               
                // циклично сдвигаем весь массив
                for (int j = 1; j < incomingArray.length - 1; j++) {
                    incomingArray[incomingArray.length - j] = incomingArray[incomingArray.length - j - 1];
                }
               
                // ставим буферный элемент в 1 ячейку
                incomingArray[1] = buffer;
            }
        }
        else if (shift < 0) {
            for (int i = 0; i > shift; n--) {
                int buffer = incomingArray[incomingArray.length - 1];
                incomingArray[incomingArray.length - 1] = incomingArray[0];
               
                for (int j = 1; j < incomingArray.length - 1; j++) {
                    incomingArray[j - 1] = incomingArray[j];
                }
               
                incomingArray[incomingArray.length - 2] = buffer;
            }
        }
    }
   
    return incomingArray;
}

Хочу отметить, что такое решение имеет место, и оно применимо. Но мы же решаем алгоритмическую задачу, поэтому неплохо бы поговорить о том, какую сложность будет иметь приведенный алгоритм. Если опустить процесс вычислений буферных элементов и обмена ими между ячейками, то сложность алгоритма сводится к O(N * M), где N — размер входного массива, а M — величина сдвига. Очевидно, что для |M| = 1 (т.е. M = -1 или M = 1) сложность снизится до O(N). Это частный случай.

Теперь давайте подумаем, что же тут не так. На самом деле, если мы знаем величину сдвига (а мы её знаем), то вполне можно вычислить, какой элемент будет следующим. Это говорит о том, что можно создать алгоритм следующего вида:

  1. Получаем нулевой элемент и кладем его в буфер
  2. Начинаем цикл от 0 до длины массива включительно (это обусловлено тем, что в момент, когда мы дойдём до последнего элемента, он будет помещен в буфер, из которого его надо восстановить на месте нулевого элемента, чем полностью закольцевать сдвиг)
  3. В каждой итерации
    1. Получаем текущий элемент
    2. Ставим на его место буферный элемент
    3. Текущий элемент сохраняем в буфер

Также будет удобно реализовать дополнительный метод расчета индекса элемента, исходя из номера шага и дельты. Для этого можно немного поработать «бумажным компилятором» — просто нарисовать на бумажке массив, подвигать элементы и вычленить закономерности. После нескольких минут/часов/дней рисования у Вас может получиться нечто похожее на формулы, приведенные ниже. При положительном сдвиге формула индекса будет выглядеть так

индекс = (номер_шага * сдвиг) % длина_массива;

А при отрицательном так

индекс = длина_массива + ((номер_шага * сдвиг) % длина_массива);

Теперь мы можем написать реализацию нашего алгоритма

public class moves {

    public static void main(String[] args){
        int[] in = {5, 3, 7, 2, 9, 13, 42};
        int[] out3 = moves(in, -1);
        printOut(out3);
    }

    /**
     * Main method, shifts array
     * @param incoming - user array
     * @param delta - shift value
     * @return int[] result array
     */
    public static int[] moves(int[] incoming, int delta){
        // won't work in case of zero shift
        if(delta != 0){
            // simplify the shift
            if(Math.abs(delta) > incoming.length){
                delta = delta % incoming.length;
            }

            int buffer = incoming[getItemIndexByStepNumber(incoming.length, delta, 0)];
            for(int i = 0; i < incoming.length+1; i++){
                int currentElementIndex = getItemIndexByStepNumber(incoming.length, delta, i);
                int currentElement = incoming[currentElementIndex];

                incoming[currentElementIndex] = buffer;
                buffer = currentElement;
            }
        }

        return incoming;
    }

    /**
     * Simple printout
     * @param incomingArray user array
     */
    public static void printOut(int[] incomingArray){
        for(int item: incomingArray){
            System.out.print(item + " ");
        }

        System.out.println();
    }

    /**
     * Returns item index within shift and number of step
     * @param incomingLength - array length
     * @param delta - shift
     * @param step - number of step
     * @return int index of the requested element
     */
    public static int getItemIndexByStepNumber(int incomingLength, int delta, int step){
        int itemIndex;

        // right move
        if(delta > 0){
            if(step == 0)
                itemIndex = 0;
            else
                itemIndex = (step * delta) % incomingLength;
        }
        // left move
        else{
            if(step == 0)
                itemIndex = 0;
            else
                itemIndex = incomingLength + ((step * delta) % incomingLength);
        }

        // reverse in case of array out of bounds
        if(itemIndex == incomingLength) itemIndex = 0;

        return itemIndex;
    }
}

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

Надеюсь, приведенные измышления будут для Вас полезны. Буду рад критике и комментариям!

Дочитавшим до конца, картинка демотиватор 🙂

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *