在 java 中旋转数组的一部分

Question

我看过很多关于如何旋转数组的例子，比方说：

[0,1,2,3,4] 如果我旋转 1 次就变成 [4,0,1,2,3]。

但是，如果我想采用初始和最终位置并且仅旋转该部分怎么办？假设我有数组

[0,1,2,3,4,5]

我想从 array[1] 旋转到 array[4] 2 次。结果将是：

[0,3,4,1,2,5]

请注意 array[0] = 0 和 array[4] = 5 根本没有改变位置。

我一直在使用 John Kurlak 的 Juggling Algorithm（public on Github），但我无法让它工作。

谁能指出我正确的方向？我找不到有关如何执行此操作的任何信息。

Answer 1

请使用下面的修改版本来做你需要的

import java.util.Arrays;

/**
 * This program rotates all of the elements in an array left by a given k
 * value.  It runs in O(n) time and uses O(1) additional space (it operates
 * in-place).
 *
 * @author      John Kurlak <john@kurlak.com>
 * @date        5/30/2013
 */
public class JugglingAlgorithm {
    /**
     * Runs the program with an example array.
     *
     * @param args      The command-line arguments.
     */
    public static void main(String[] args) {
        int[] array = new int[] { 0,1,2,3,4,5 };
        int k = 2;

        System.out.println(Arrays.toString(array));
        System.out.println("rotated to the left " + k + " is:");
        rotateArrayLeft(array, k, 1, 4);
        System.out.println(Arrays.toString(array));
    }

    /**
     * Rotates all of the elements in an array left by the given k value.
     * If k is negative, it rotates the elements in the array right.
     * This method modifies the array in place, so it does not return
     * anything.
     *
     * @param array The array to shift.
     * @param k     The number of indices by which to shift the array.
     */
    public static void rotateArrayLeft(int[] array, int k, int minIndex, int maxIndex) {
        if (array == null) {
            return;
        }

        int n = maxIndex - minIndex + 1;

        // Handle negative k values (rotate to right)
        if (k < 0) {
            k = n - Math.abs(k);
        }

        // Ensure k is in interval [0, n)
        k = ((k % n) + n) % n;

        // Perform juggling algoritm
        for (int i = 0, gcd = gcd(k, n); i < gcd; i++) {
            int temp = array[i+minIndex];
            int j = i;

            while (true) {
                int p = j + k;

                if (p >= n) {
                    p = p - n;
                }

                if (p == i) {
                    break;
                }

                array[j +minIndex] = array[p+minIndex];
                j = p;
            }

            array[j +minIndex] = temp;
        }
    }

    /**
     * Uses Euclid's algorithm to find the greatest common divisor of
     * two numbers.
     *
     * @param a     The first number.
     * @param b     The second number.
     * @returns     The great common divisor of `a` and `b`.
     */
    public static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }
}

在 java 中旋转数组的一部分

Rotate portion of an array in java

arrays

rotation