Keer een array om in groepen van een bepaalde grootte
Gegeven een array arr[] en een geheel getal k vind de array na het omkeren van elke subarray van opeenvolgende k-elementen op hun plaats. Als de laatste subarray minder dan k elementen heeft, keert u deze om zoals deze is. Wijzig de array op zijn plaats en retourneer niets.
Voorbeelden:
Invoer: arr[] = [1 2 3 4 5 6 7 8] k = 3
Uitgang: [3 2 1 6 5 4 8 7]
Uitleg: Elementen zijn omgekeerd: [1 2 3] → [3 2 1] [4 5 6] → [6 5 4] en de laatste groep [7 8](grootte < 3) is reversed as [8 7].Invoer: arr[] = [1 2 3 4 5] k = 3
Uitvoer: [3 2 1 5 4]
Toelichting: Eerste groep bestaat uit elementen 1 2 3. Tweede groep bestaat uit 4 5.I nvoer: arr[] = [5 6 8 9] k = 5
Uitgang: [9 8 6 5]
Uitleg: Omdat k groter is dan de arraygrootte, is de hele array omgekeerd.
[Benadering ] Omkering van groepen met een vaste omvang
Het idee is om elke subarray van grootte k te beschouwen, beginnend bij het begin van de array, en deze om te draaien. We moeten een aantal speciale gevallen behandelen.
=> Als k geen veelvoud is van n, waarbij n de grootte is van de array voor de laatste groep, hebben we minder dan k elementen over. We moeten alle resterende elementen omkeren.
=> Als k = 1 moet de array ongewijzigd blijven. Als k >= n keren we alle elementen in de array om.Om een subarray om te keren, moet u twee pointers gebruiken: links en rechts. Verwissel nu de elementen bij de linker- en rechteraanwijzer en verhoog de linker- en rechteraanwijzer met 1 en verlaag de rechteraanwijzer met 1. Herhaal dit totdat de linker- en rechteraanwijzers elkaar niet kruisen.
Werkend:
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 ( ' ' ));
Uitvoer
3 2 1 6 5 4 8 7
Tijdcomplexiteit: O(n) we doorlopen de hele array slechts één keer en keren elementen om in groepen van grootte k. Omdat we geen enkel element opnieuw bekijken, groeit het totale werk lineair met de grootte van de array. Dus als de array n elementen heeft, zijn er ongeveer n stappen nodig.
Hulpruimte: O(1) de omkering gebeurt direct binnen de originele array met slechts een paar extra variabelen.
