Вращение массива по положению n

  

Вход 1,2,3,4,5,6,7,8

     

Если rotateOrder = 2

     

Выход должен быть 7,8,1,2,3,4,5,6

     

Если rotateOrder = 3

     

Выход должен быть 6,7,8,1,2,3,4,5

Вот моя программа:

int [] unOrderedArr = {1,2,3,4,5,6,7,8};
        int  orderToRotate =2;

       for(int i = 0; i<orderToRotate; i++){

           for(int j = unOrderedArr.length-1; j>0; j--){
               int temp = unOrderedArr[j];
               unOrderedArr[j] = unOrderedArr[j-1];
               unOrderedArr[j-1] = temp;

           }

        }

       for(int j = 0; j<unOrderedArr.length; j++){
         System.out.println("element is " + unOrderedArr[j]);

           }

Как его можно оптимизировать?

12 голосов | спросил M Sach 9 72014vEurope/Moscow11bEurope/MoscowSun, 09 Nov 2014 15:19:32 +0300 2014, 15:19:32

6 ответов


12

Подтвердите свои входы

Текущий метод не проверяет наличие недопустимого ввода:

  • null массив
  • отрицательный порядок вращения

Я предлагаю добавить это объявление вверху:

if (arr == null || order < 0) {
    throw new IllegalArgumentException("The array must be non-null and the order must be non-negative");
}

Следуйте стандартным форматам

Опубликованный код грязный. Используйте среду IDE для ее форматирования до стандарта:

int[] unOrderedArr = {1, 2, 3, 4, 5, 6, 7, 8};
int orderToRotate = 2;

for (int i = 0; i < orderToRotate; i++) {
    for (int j = unOrderedArr.length - 1; j > 0; j--) {
        int temp = unOrderedArr[j];
        unOrderedArr[j] = unOrderedArr[j - 1];
        unOrderedArr[j - 1] = temp;
    }
}

Теперь это намного легче читать.

В соответствующей заметке простой способ печати массива состоит в использовании Arrays.toString

Оптимизация

Фрист всех, что произойдет, если вы получите arr для поворота, а порядок вращения = arr.length? Элементы массива будут вращаться бессмысленно, просто чтобы вернуться в исходное положение. Это становится еще хуже для кратных arr.length.

Во-вторых, в этом коде:

for (int i = 0; i < order; i++) {
    for (int j = arr.length - 1; j > 0; j--) {
        // ...
    }
}

Вышеупомянутый код выполняет итерацию по всему массиву order раз.

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

Рекомендуемая реализация

Приведенные выше предложения и некоторые улучшения стиля:

private static void rotate(int[] arr, int order) {
    if (arr == null || order < 0) {
        throw new IllegalArgumentException("The array must be non-null and the order must be non-negative");
    }
    int offset = arr.length - order % arr.length;
    if (offset > 0) {
        int[] copy = arr.clone();
        for (int i = 0; i < arr.length; ++i) {
            int j = (i + offset) % arr.length;
            arr[i] = copy[j];
        }
    }
}

Некоторые модульные тесты для проверки работы:

@Test
public void testRotateBy2() {
    int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
    int[] expected = {7, 8, 1, 2, 3, 4, 5, 6};
    rotate(arr, 2);
    assertArrayEquals(expected, arr);
}

@Test
public void testRotateBy3() {
    int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
    int[] expected = {6, 7, 8, 1, 2, 3, 4, 5};
    rotate(arr, 3);
    assertArrayEquals(expected, arr);
}

@Test
public void testRotateByLength() {
    int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
    int[] expected = arr.clone();
    rotate(arr, arr.length);
    assertArrayEquals(expected, arr);
    rotate(arr, arr.length * 3);
    assertArrayEquals(expected, arr);
}

@Test
public void testRotateByZero() {
    int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
    int[] expected = arr.clone();
    rotate(arr, 0);
    assertArrayEquals(expected, arr);
}
ответил janos 9 72014vEurope/Moscow11bEurope/MoscowSun, 09 Nov 2014 17:06:45 +0300 2014, 17:06:45
3

Я бы использовал другой алгоритм. Создайте новый массив и скопируйте данные из старого со смещением:

int[] rotate(final int[] unOrderedArr, final int orderToRotate) {
    final int length = unOrderedArr.length;
    final int[] rotated = new int[length];
    for (int i = 0; i < length; i++) {
        rotated[(i + orderToRotate) % length] = unOrderedArr[i];
    }
    return rotated;
}

Он должен быть как проще, так и быстрее - особенно для больших массивов и больших смещений. Единственным недостатком является то, что вам нужно выделить дополнительный массив. Для небольших смещений это может быть узким местом. Но, как всегда, сначала нужно ориентироваться и определить, какие из них стоит оптимизировать.

ответил Banthar 9 72014vEurope/Moscow11bEurope/MoscowSun, 09 Nov 2014 15:55:09 +0300 2014, 15:55:09
3

Существует четкая реализация (далее «Программирование жемчуга»), которая не требует временного хранения.

Предположим, что у вас есть метод reverse(int[] array, int i, int, j), который меняет часть массива между i и j (включительно). Затем rotate(int[] array, int rotateOrder) реализуется (пропущенные граничные проверки для верности):

public rotate(int[] array, int k) {
    int lastIndex = array.length-1;

    reverse(array, 0, lastIndex);
    reverse(array, 0, rotateOrder-1);
    reverse(array, rotateOrder, lastIndex);
}


public void reverse(int[] a, int i , int j) {
    int ii =  i;
    int jj = j;

    while (ii < jj) {
        swap(ii, jj, a);
        ++ii;
        --jj;
    }
}

Если вызов reverse(array, 0, lastIndex) будет последним, вы получите поворот в обратном направлении

ответил David Soroko 30 J0000006Europe/Moscow 2015, 15:16:43
1

В соответствии с рассматриваемым кодом для получения данных требуется три цикла. Здесь я использую только один цикл для получения элемента, который мы хотим поменять. Использование java-скрипта в встроенных функциях для получения элементов, которые мы не хотим менять.

Итак, шаги следующие:

  1. Получить массив, который мы не хотим менять в массиве temp.
  2. Элемент проверки погоды не должен превышать фактическую длину массива
  3. Элемент массива Loop, который мы меняем в результирующем массиве (результат)
  4. Конец цикла
  5. Конкат нового массива с массивом срезов для получения результирующего результата.
  6. Результат печати

    var numberArr = [1, 2, 3, 4, 5, 6];
    var maxLength = numberArr.length;
    var swapBy = 2;
    var temp = numberArr.slice(0, (maxLength - swapBy));
    var result = [];
    if(swapBy > maxLength) {
      alert("Sorry : Please enter proper  value");
    }
    for(var i = (maxLength - swapBy); i < maxLength; i++) {
      result.push(numberArr[i]);
    }
    result.concat(temp);
    //output will be
    //[5, 6 ,1, 2, 3, 4]
    

Я думаю, что это оптимизирует время решения, а также пространство

ответил Harshal Shinde 3 J0000006Europe/Moscow 2015, 10:09:37
1

Дополнительная перестановка решения. Включает оптимизацию, уменьшающую количество циклов, необходимых, если они превышают длину массива

private int[] getCyclicInts(int[] A, int K) {
    if (A == null)
        return A;

    if (A.length <= 1)
        return A;

    if (K <= 0)
        return A;

    //make sure we don't do unneeded loops.
    int actualIteration = K;
    if (actualIteration >= A.length){
        actualIteration = actualIteration % A.length;
    }

    if (actualIteration == 0)
        return A;

    int []  array = new int [A.length];

    int index = 0;
    for (int i=A.length - actualIteration  ; i < A.length; i++){
        array[index] = A[i];
        index ++;
    }

    for (int i=0 ; i < A.length - actualIteration; i++){
        array[index] = A[i];
        index ++;
    }

    return array;
}
ответил dogood 19 62016vEurope/Moscow11bEurope/MoscowSat, 19 Nov 2016 21:46:35 +0300 2016, 21:46:35
0

Ниже приведена временная сложность \ $ O (n) \ $. Я рассматриваю его как оптимизированную версию принятого решения, так как в принятом решении мы делаем копию полного массива, но в нижеследующем решении я только копирую требуемые элементы, а не все. Так что лучше будет сложность пространства памяти, хотя худшим может быть \ $ O (n) \ $:

public static void main(String[] args) {
    int[] unOrderedArr = { 1, 2, 3, 4, 5, 6, 7, 8 };
    int rotationOrder = 3;

    /**
     * this will store the last n elements which need to be shifted in
     * beginning
     **/

    if (unOrderedArr.length != rotationOrder) {

        int[] temp = new int[rotationOrder];
        int tempPointer = unOrderedArr.length - rotationOrder;

        for (int i = 0; i < temp.length; ++i) {
            temp[i] = unOrderedArr[tempPointer++];

        }

        for (int i = unOrderedArr.length - rotationOrder - 1; i >= 0; --i) {

            unOrderedArr[i + rotationOrder] = unOrderedArr[i];
        }

        for (int i = 0; i < temp.length; ++i) {
            unOrderedArr[i] = temp[i];

        }
    }

    // print the output
    for (int i = 0; i < unOrderedArr.length; ++i) {
        System.out.println(unOrderedArr[i]);

    }

}
ответил dogood 19 62016vEurope/Moscow11bEurope/MoscowSat, 19 Nov 2016 21:46:35 +0300 2016, 21:46:35

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132