Invertire un array in gruppi di determinata dimensione
Dato un array arr[] e un numero intero k trova l'array dopo aver invertito ogni sottoarray di k elementi consecutivi al suo posto. Se l'ultimo sottoarray ha meno di k elementi, invertirlo così com'è. Modificare l'array sul posto non restituisce nulla.
Esempi:
Ingresso: arr[] = [1 2 3 4 5 6 7 8] k = 3
Produzione: [3 2 1 6 5 4 8 7]
Spiegazione: Gli elementi sono invertiti: [1 2 3] → [3 2 1] [4 5 6] → [6 5 4] e l'ultimo gruppo [7 8](dimensione < 3) is reversed as [8 7].Ingresso: arr[] = [1 2 3 4 5] k = 3
Uscita: [3 2 1 5 4]
Spiegazione: Il primo gruppo è composto dagli elementi 1 2 3. Il secondo gruppo è composto da 4 5.IO inserire: arr[] = [5 6 8 9] k = 5
Produzione: [9 8 6 5]
Spiegazione: Poiché k è maggiore della dimensione dell'array, l'intero array viene invertito.
[Approccio ] Inversione di gruppi di dimensioni fisse
L'idea è quella di considerare ogni sotto-array di dimensione k partendo dall'inizio dell'array e invertirlo. Dobbiamo gestire alcuni casi speciali.
=> Se k non è un multiplo di n dove n è la dimensione dell'array per l'ultimo gruppo, avremo meno di k elementi rimasti, dobbiamo invertire tutti gli elementi rimanenti.
=> Se k = 1 l'array dovrebbe rimanere invariato. Se k >= n invertiamo tutti gli elementi presenti nell'array.Per invertire un sottoarray mantenere due puntatori: sinistro e destro. Ora scambia gli elementi sui puntatori sinistro e destro e aumenta a sinistra di 1 e diminuisci a destra di 1. Ripeti finché i puntatori sinistro e destro non si incrociano.
Lavorando:
C++ #include #include using namespace std ; void reverseInGroups ( vector < int >& arr int k ){ // Get the size of the array int n = arr . size (); for ( int i = 0 ; i < n ; i += k ) { int left = i ; // to handle case when k is not multiple of n int right = min ( i + k - 1 n - 1 ); // reverse the sub-array [left right] while ( left < right ) { swap ( arr [ left ++ ] arr [ right -- ]); } } } int main () { vector < int > arr = { 1 2 3 4 5 6 7 8 }; int k = 3 ; reverseInGroups ( arr k ); for ( int num : arr ) cout < < num < < ' ' ; return 0 ; }
C #include void reverseInGroups ( int arr [] int n int k ){ for ( int i = 0 ; i < n ; i += k ) { int left = i ; int right ; // to handle case when k is not multiple // of n if ( i + k -1 < n -1 ) right = i + k -1 ; else right = n -1 ; // reverse the sub-array [left right] while ( left < right ) { // swap int temp = arr [ left ]; arr [ left ] = arr [ right ]; arr [ right ] = temp ; left ++ ; right -- ; } } } int main () { int arr [] = { 1 2 3 4 5 6 7 8 }; int k = 3 ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); reverseInGroups ( arr n k ); for ( int i = 0 ; i < n ; i ++ ) printf ( '%d ' arr [ i ]); return 0 ; }
Java class GfG { static void reverseInGroups ( int [] arr int k ){ int n = arr . length ; for ( int i = 0 ; i < n ; i += k ) { int left = i ; int right = Math . min ( i + k - 1 n - 1 ); // reverse the sub-array while ( left < right ) { int temp = arr [ left ] ; arr [ left ] = arr [ right ] ; arr [ right ] = temp ; left ++ ; right -- ; } } } public static void main ( String [] args ) { int [] arr = { 1 2 3 4 5 6 7 8 }; int k = 3 ; reverseInGroups ( arr k ); for ( int num : arr ) { System . out . print ( num + ' ' ); } } }
Python def reverseInGroups ( arr k ): i = 0 # get the size of the array n = len ( arr ) while i < n : left = i # To handle case when k is not # multiple of n right = min ( i + k - 1 n - 1 ) # reverse the sub-array [left right] while left < right : arr [ left ] arr [ right ] = arr [ right ] arr [ left ] left += 1 right -= 1 i += k if __name__ == '__main__' : arr = [ 1 2 3 4 5 6 7 8 ] k = 3 reverseInGroups ( arr k ) print ( ' ' . join ( map ( str arr )))
C# using System ; class GfG { public static void reverseInGroups ( int [] arr int k ){ int n = arr . Length ; for ( int i = 0 ; i < n ; i += k ) { int left = i ; // to handle case when k is // not multiple of n int right = Math . Min ( i + k - 1 n - 1 ); int temp ; // reverse the sub-array [left right] while ( left < right ) { temp = arr [ left ]; arr [ left ] = arr [ right ]; arr [ right ] = temp ; left += 1 ; right -= 1 ; } } } public static void Main ( string [] args ){ int [] arr = new int [] { 1 2 3 4 5 6 7 8 }; int k = 3 ; int n = arr . Length ; reverseInGroups ( arr k ); for ( int i = 0 ; i < n ; i ++ ) { Console . Write ( arr [ i ] + ' ' ); } } }
JavaScript function reverseInGroups ( arr k ) { let n = arr . length ; for ( let i = 0 ; i < n ; i += k ) { let left = i ; // to handle case when k is not // multiple of n let right = Math . min ( i + k - 1 n - 1 ); // reverse the sub-array [left right] while ( left < right ) { // Swap elements [ arr [ left ] arr [ right ]] = [ arr [ right ] arr [ left ]]; left += 1 ; right -= 1 ; } } return arr ; } // Driver Code let arr = [ 1 2 3 4 5 6 7 8 ]; let k = 3 ; let arr1 = reverseInGroups ( arr k ); console . log ( arr1 . join ( ' ' ));
Produzione
3 2 1 6 5 4 8 7
Complessità temporale: O(n) percorriamo l'intero array una sola volta invertendo gli elementi in gruppi di dimensione k. Poiché non rivisitiamo alcun elemento, il lavoro totale svolto cresce linearmente con la dimensione dell'array. Quindi se l'array ha n elementi occorrono circa n passaggi.
Spazio ausiliario: O(1) l'inversione viene eseguita direttamente all'interno dell'array originale utilizzando solo poche variabili extra.
