Invertir una matriu en grups de mida determinada
Donada una matriu arr[] i un nombre enter k Trobeu la matriu després d'invertir cada subarranjament de k elements consecutius al seu lloc. Si l'últim subbarray té menys de k elements, inverteix-lo tal com és. Modificar la matriu al seu lloc no retorna res.
Exemples:
Entrada: arr[] = [1 2 3 4 5 6 7 8] k = 3
Sortida: [3 2 1 6 5 4 8 7]
Explicació: Els elements s'inverteixen: [1 2 3] → [3 2 1] [4 5 6] → [6 5 4] i l'últim grup [7 8](mida < 3) is reversed as [8 7].Entrada: arr[] = [1 2 3 4 5] k = 3
Sortida: [3 2 1 5 4]
Explicació: el primer grup està format pels elements 1 2 3. El segon grup està format per 4 5.jo nentrada: arr[] = [5 6 8 9] k = 5
Sortida: [9 8 6 5]
Explicació: Com que k és més gran que la mida de la matriu, la matriu sencera s'inverteix.
[Aproximació ] Inversió de grups de mida fixa
La idea és considerar cada submatriu de mida k començant des del principi de la matriu i invertir-la. Hem de tractar alguns casos especials.
=> Si k no és múltiple de n on n és la mida de la matriu per a l'últim grup, ens quedaran menys de k elements, haurem d'invertir tots els elements restants.
=> Si k = 1, la matriu hauria de romandre sense canvis. Si k >= n revertem tots els elements presents a la matriu.Per invertir un subbarrat mantingueu dos punters: esquerra i dreta. Ara intercanvieu els elements dels punters esquerre i dret i incrementeu l'esquerra en 1 i disminuïu la dreta en 1. Repetiu fins que els punters esquerre i dret no es creuen.
Treballant:
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 ( ' ' ));
Sortida
3 2 1 6 5 4 8 7
Complexitat temporal: O(n) recorrem tota la matriu només una vegada invertint elements en grups de mida k. Com que no revisem cap element, el treball total realitzat creix linealment amb la mida de la matriu. Per tant, si la matriu té n elements, pren aproximadament n passos.
Espai auxiliar: O(1) la inversió es fa directament dins de la matriu original utilitzant només unes quantes variables addicionals.
