주어진 크기의 그룹으로 배열을 뒤집습니다.
배열이 주어지면 도착[] 그리고 정수 케이 연속된 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으로 구성됩니다. 두 번째 그룹은 4 5로 구성됩니다.나 입력: arr[] = [5 6 8 9] k = 5
산출: [9 8 6 5]
설명: k가 배열 크기보다 크므로 전체 배열이 반전됩니다.
[접근하다 ] 고정 크기 그룹 반전
아이디어는 배열의 시작 부분부터 시작하여 크기가 k인 모든 하위 배열을 고려하고 이를 반대로 하는 것입니다. 우리는 몇 가지 특별한 경우를 처리해야 합니다.
=> k가 n의 배수가 아닌 경우(여기서 n은 마지막 그룹의 배열 크기임) k개 미만의 요소가 남게 되며 나머지 요소를 모두 반대로 해야 합니다.
=> k = 1이면 배열은 변경되지 않은 상태로 유지되어야 합니다. k >= n이면 배열에 있는 모든 요소를 반전시킵니다.하위 배열을 반전하려면 왼쪽과 오른쪽의 두 포인터를 유지하십시오. 이제 왼쪽과 오른쪽 포인터의 요소를 바꾸고 왼쪽으로 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 그룹의 요소를 반전하여 전체 배열을 한 번만 살펴봅니다. 어떤 요소도 다시 방문하지 않기 때문에 수행된 전체 작업은 배열 크기에 따라 선형적으로 증가합니다. 따라서 배열에 n개의 요소가 있으면 대략 n 단계가 소요됩니다.
보조 공간: O(1) 반전은 몇 가지 추가 변수를 사용하여 원래 배열 내에서 직접 수행됩니다.
