Как поменять суб-массив

Question

Как переставить подмассив целых чисел (для случайного m) без вспомогательного массива, как это?

example input [1,2,3,4,5,6,7,8,9,10]            
m=3;             
expected output :
[4,5,6,7,8,9,10,1,2,3]

example input : 
[1,2,3,4,5]            
m=4
example output         
[5,1,2,3,4]   

example input :
[1,2,3,4,5,6]        
m=2              
example output
[3,4,5,6,1,2]  

Я попытался создать временный массив, и это сработало, но можно ли сделать больше памяти эффективный.

Спасибо.

Answer 1

Да, вы можете решить это за O(n) время и O(1) пространство. Это включает в себя обращение подмассивов.

Давайте возьмем в качестве примера один из них:

[1,2,3,4,5,6,7,8,9,10]

m = 3

• Имеют 2 указателя и меняют первый и последний элемент, второй со вторым последним и так далее. Итак, в приведенном выше примере наш массив будет выглядеть так:

  [10,  9,  8,  4,  5,  6,  7,  3,  2,  1]
   ----------                   ---------
        A                           C
                -------------
                      B
  

• Важно: Если значение m больше половины размера массив, вы бы остановили обмен там сам.

• В приведенном выше сценарии мы успешно разделили массив на 3 части, которые я назвал A, B и C.

• Теперь обратная часть C. Теперь эта часть вычислена.

  [10,  9,  8,  4,  5,  6,  7,  1,  2,  3]
   ----------                   
        A                           
                -------------
                      B
  

• Обратная часть B, которая будет выглядеть так:

  [10,  9,  8,  7,  6,  5,  4,  1,  2,  3]
   ----------                   
        A                           
                -------------
                      B
  

• Теперь, переверните всю часть (B + A), которая является вашим окончательным результатом.

  [4,  5,  6,  7,  8,  9,  10,  1,  2,  3]
  

Примечание: Иногда, возможно, эта часть B не будет существовать Таким образом, в этом случае вы просто изменили бы весь массив A (или можете добавить дополнительные условия)

Фрагмент:

     private static void rotateArray(int[] arr,int m){
        int left = 0,right = arr.length - 1;
        int limit = Math.min(m,arr.length/2);
        while(left < limit){
            swap(arr,left++,right--);
        }

        reverse(arr,arr.length - m,arr.length-1);
        reverse(arr,m,arr.length-m-1);
        reverse(arr,0,arr.length-m-1);
    }

    private static void reverse(int[] arr,int left,int right){
        while(left < right){
           swap(arr,left++,right--);
        }
    }

    private static void swap(int[] arr,int x,int y){
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }

Демонстрация : https://onlinegdb.com/HklMoZKG4U

Answer 2

Вопрос похож на вращение массива в левом направлении ... Прежде чем читать решение, попробуйте применить это ... Я повернул массив без использования дополнительного пробела .. Код выглядит следующим образом ..

 #include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,rot,lpos=0;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
         cin>>arr[i];
    cin>>rot;    // number of times to rotate
    int num=0,tmp,ntmp=arr[0],npos,pos=0;
    while(1)
    {
            npos=pos-rot;  // new position of element at position pos
            if(npos<0)
            {
                npos=n-rot+pos;
            }
            tmp=arr[npos];  // saved the element at npos
            arr[npos]=ntmp;
            ntmp=tmp;
            num++;
            if(num==n) // if first position again occours then exit
                break;
            if(npos==lpos)
                {
                    lpos++;
                    pos=lpos;
                    ntmp=arr[pos];
                }
                else
            pos=npos;
    }
    for(int i=0;i<n;i++)
            cout<<arr[i];
    return 0;
}

Answer 3

Это так же просто, как смещение элемента с 0-го индекса на последний индекс после смещения оставшихся элементов на одну позицию влево, m раз.

Программа:

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int input[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        int m = 3;
        int temp, i, j;
        for (i = 1; i <= m; i++) { // m times
            temp = input[0];
            for (j = 1; j < input.length; j++) {
                input[j - 1] = input[j];
            }
            input[input.length - 1] = temp;
        }
        System.out.println(Arrays.toString(input));
    }
}

Вывод:

[4, 5, 6, 7, 8, 9, 10, 1, 2, 3]

Не стесняйтесь комментировать в случае сомнений.