عكس صفيف في مجموعات ذات حجم معين
نظرا لمجموعة وصول[] وعدد صحيح ك ابحث عن المصفوفة بعد عكس كل مصفوفة فرعية من عناصر k المتتالية في مكانها. إذا كانت المصفوفة الفرعية الأخيرة تحتوي على أقل من عناصر k، قم بعكسها كما هي. تعديل المصفوفة في مكانها لا يعود بأي شيء.
أمثلة:
مدخل: آر[] = [1 2 3 4 5 6 7 8] ك = 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].مدخل: آر[] = [1 2 3 4 5] ك = 3
الإخراج: [3 2 1 5 4]
شرح: المجموعة الأولى تتكون من العناصر 1 2 3. المجموعة الثانية تتكون من 4 5.أنا نبوت: آر[] = [5 6 8 9] ك = 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) يتم الانعكاس مباشرة داخل المصفوفة الأصلية باستخدام عدد قليل من المتغيرات الإضافية.
