指定されたサイズのグループごとに配列を反転します
配列が与えられた場合 到着[] そして整数 k 連続する k 要素のすべての部分配列を所定の位置に反転した後、配列を検索します。最後の部分配列の要素が k 未満の場合は、そのまま反転します。配列を適切に変更しても、何も返されません。
例:
入力： arr[] = [1 2 3 4 5 6 7 8] k = 3
出力： [3 2 1 6 5 4 8 7]
説明： 要素が反転します: [1 2 3] → [3 2 1] [4 5 6] → [6 5 4] と最後のグループ [7 8](サイズ < 3) is reversed as [8 7].入力： arr[] = [1 2 3 4 5] k = 3
出力: [3 2 1 5 4]
説明: 最初のグループは要素 1 2 3 で構成されます。2 番目のグループは 4 5 で構成されます。私 入力: arr[] = [5 6 8 9] k = 5
出力： [9 8 6 5]
説明： k は配列サイズより大きいため、配列全体が反転されます。
[アプローチ ] 固定サイズのグループ反転
アイデアは、配列の先頭から始めてサイズ k のすべての部分配列を考慮し、それを逆にすることです。いくつかの特殊なケースに対処する必要があります。
=> k が n の倍数でない場合 (n は最後のグループの配列のサイズ)、残っている要素は k 未満になるため、残りの要素をすべて反転する必要があります。
=> k = 1 の場合、配列は変更されないままでなければなりません。 k >= n の場合、配列内に存在するすべての要素が反転されます。部分配列を反転するには、左と右の 2 つのポインタを維持します。ここで、左ポインタと右ポインタの要素を交換し、左に 1 ずつインクリメントし、右に 1 だけデクリメントします。左と右のポインタが交差しなくなるまで繰り返します。
働く：
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 ( ' ' ));
出力
3 2 1 6 5 4 8 7
時間計算量: O(n) サイズ k のグループ内の要素を 1 回だけ反転して配列全体を調べます。どの要素も再検討しないため、実行される総作業量は配列のサイズに比例して増加します。したがって、配列に n 個の要素がある場合、およそ n ステップかかります。
補助スペース: O(1) 反転は、いくつかの追加の変数を使用して、元の配列内で直接行われます。
