Как исправить этот код для Java, чтобы вращать массив для больших массивов и большого числа вращений? - PullRequest
0 голосов
/ 26 сентября 2019

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

Не работает для больших значений размера массива и элемента вращения.

следующий код работает для 15 элементов массива и поворачивается на 11 чисел (я не пробовал для более высоких чисел), но он не работает для элемента массива 77 и для поворота на 69 чисел.Работает как с отсортированным, так и с несортированным массивом.Почему он не работает и как я могу это исправить?

int dupRotate = D;

for(int j=N-1; j>=0; --j) {

    /* checks whether loop is to be stopped or not.
       bottom condition fails to stop the 1st iteration for 
       third loop run.
    */     
    if(dupRotate == 0) {
        break;
    }

    /* Exchanges elements here.
       for loop run1 - 
       arr = 1,2,3,4,5
       after j reaches index 1
       arr = 2,3,4,5,1.

       for loop run2 -
       arr = 2,3,4,5,1.
       after j reaches index 1
       arr = 3,4,5,1,2.
    */ 
    int temp = arr[0];
    arr[0] = arr[j];
    arr[j] = temp;

    /* if j reaches 1
       decrements dupRotate and sets j = N 
       then for loop decrements j and starts loop again.
    */     

    if(j == 1 && dupRotate > 0) {
        dupRotate--;
        j = N;
    }

}
77 69
40 13 27 87 95 40 96 71 35 79 68 2 98 3 18 93 53 57 2 81 87 42 66 90 45 20 41 30 32 18 98 72 82 76 10 28 68 57 98 54 87 66 7 84 20 25 29 72 33 30 4 20 71 69 9 16 41 50 97 24 19 46 47 52 22 56 80 89 65 29 42 51 94 1 35 65 25

Правильный вывод:

29 42 51 94 1 35 65 25 40 13 27 87 95 40 96 71 35 79 68 2 98 3 18 93 53 57 2 81 87 42 66 90 45 20 41 30 32 18 98 72 82 76 10 28 68 57 98 54 87 66 7 84 20 25 29 72 33 30 4 20 71 69 9 16 41 50 97 24 19 46 47 52 22 56 80 89 65

А вывод вашего кода:

45 20 41 30 32 18 98 72 82 76 10 28 68 57 98 54 87 66 7 84 20 25 29 72 33 30 4 20 71 69 9 16 41 50 97 24 19 46 47 52 22 56 80 89 65 29 42 51 94 1 35 65 69 40 13 27 87 95 40 96 71 35 79 68 2 98 3 18 93 53 57 2 81 87 42 66 90

Ответы [ 2 ]

1 голос
/ 26 сентября 2019

Довольно сложно понять вашу проблему.Я должен добавить больше описания.

Я думаю, если вы используете правильный алгоритм вращения массива, то это не зависит от длины массива.Это один из самых эффективных алгоритмов:

[1,2,3,4,5] -> k = 2 -> [4,5,1,2,3]
-----------------------------------
1. [1,2,3,4,5] -> [5,4,3,2,1] 
2. [5,4,3,2,1] -> [4,5,3,2,1]
3. [4,5,3,2,1] -> [4,5,1,2,3]

public static void rotate(int[] arr, int k) {
    if ((k %= arr.length) != 0) {
        k = k < 0 ? arr.length + k : k;
        swapSubArr(arr, 0, arr.length);               // 1.
        swapSubArr(arr, 0, arr.length - k);           // 2.
        swapSubArr(arr, arr.length - k, arr.length);  // 3.
    }
}

private static void swapSubArr(int[] arr, int from, int to) {
    for (int i = from, j = to - 1; i < j; i++, j--)
        swap(arr, i, j);
}

private static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}
0 голосов
/ 26 сентября 2019

Шаг за шагом

[1,2,3,4,5] -> k = 3 -> [4,5,1,2,3]
-----------------------------------
1. [1,2,3,4,5] -> [5,4,3,2,1] 
2. [5,4,3,2,1] -> [4,5,3,2,1]
3. [4,5,3,2,1] -> [4,5,1,2,3]

Код

static void rotate(int arr[], int k) {
    for (int i = 1; i <= k; i++) {
        move(arr);
    }
}

static void move(int arr[]) {
    int i, n, tmp;
    n = arr.length;
    tmp = arr[0];
    for (i = 0; i < n - 1; i++) {
        arr[i] = arr[i + 1];
    }
    arr[i] = tmp;
}

public static void main(String[] args) {
    int arr[] = { 1, 2, 3, 4, 5 };
    int k = 3;
    // [1, 2, 3, 4, 5]
    rotate(arr, k);
    // [4, 5, 1, 2, 3]
}
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...