Inverser un tableau en groupes de taille donnée
Étant donné un tableau arr[] et un entier k trouvez le tableau après avoir inversé chaque sous-tableau de k éléments consécutifs en place. Si le dernier sous-tableau contient moins de k éléments, inversez-le tel quel. Modifier le tableau en place ne renvoie rien.
Exemples :
Saisir: arr[] = [1 2 3 4 5 6 7 8] k = 3
Sortir: [3 2 1 6 5 4 8 7]
Explication: Les éléments sont inversés : [1 2 3] → [3 2 1] [4 5 6] → [6 5 4] et le dernier groupe [7 8] (taille < 3) is reversed as [8 7].Saisir: arr[] = [1 2 3 4 5] k = 3
Sortie : [3 2 1 5 4]
Explication : Le premier groupe est composé des éléments 1 2 3. Le deuxième groupe est composé de 4 5.je nentrée : arr[] = [5 6 8 9] k = 5
Sortir: [9 8 6 5]
Explication: Puisque k est supérieur à la taille du tableau, le tableau entier est inversé.
[Approche ] Inversion de groupe de taille fixe
L'idée est de considérer chaque sous-tableau de taille k en commençant par le début du tableau et de l'inverser. Nous devons gérer certains cas particuliers.
=> Si k n'est pas un multiple de n où n est la taille du tableau pour le dernier groupe, il nous restera moins de k éléments, nous devons inverser tous les éléments restants.
=> Si k = 1, le tableau doit rester inchangé. Si k >= n nous inversons tous les éléments présents dans le tableau.Pour inverser un sous-tableau, maintenez deux pointeurs : gauche et droite. Maintenant, échangez les éléments des pointeurs gauche et droit et incrémentez à gauche de 1 et décrémentez à droite de 1. Répétez jusqu'à ce que les pointeurs gauche et droit ne se croisent pas.
Fonctionnement:
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 ( ' ' ));
Sortir
3 2 1 6 5 4 8 7
Complexité temporelle : O(n) nous parcourons l’ensemble du tableau une seule fois en inversant les éléments en groupes de taille k. Puisque nous ne revisitons aucun élément, le travail total effectué augmente linéairement avec la taille du tableau. Donc, si le tableau comporte n éléments, cela prend environ n étapes.
Espace auxiliaire : O(1) l'inversion est effectuée directement dans le tableau d'origine en utilisant seulement quelques variables supplémentaires.
