算法设计：如何反转给定大小的组中的数组？

本文概述

• 建议：在继续解决方案之前, 请先在"实践"上解决它。
• C ++
• Java
• Python3
• C#
• 的PHP

给定一个数组, 反转由连续的k个元素形成的每个子数组。

例子：

输入：arr = [1、2、3、4、5、6、7、8、9] k = 3输出：[3、2、1、6、5、4、9、8、7]输入：arr = [1、2、3、4、5、6、7、8] k = 5输出：[5、4、3、2、1、8、7、6]输入：arr = [1、2、3 , 4, 5, 6] k = 1输出：[1, 2, 3, 4, 5, 6]输入：arr = [1, 2, 3, 4, 5, 6, 7, 8] k = 10输出：[8、7、6、5、4、3、2、1]

推荐：请在"实践首先, 在继续解决方案之前。

方法：考虑大小的每个子数组ķ从数组的开头开始并将其反转。我们需要处理一些特殊情况。如果k不是n的倍数, 其中n是数组的大小, 那么对于最后一组, 我们剩下的元素少于k个, 我们需要反转所有剩余的元素。如果k = 1, 数组应保持不变。如果k> = n, 则反转数组中存在的所有元素。

下图是上述方法的模拟：

下面是上述方法的实现：

C ++

// C++ program to reverse every sub-array formed by
// consecutive k elements
#include <iostream>
using namespace std;
  
// Function to reverse every sub-array formed by
// consecutive k elements
void reverse( int arr[], int n, int k)
{
     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--]);
  
     }
}
  
// Driver code
int main()
{
     int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
     int k = 3;
  
     int n = sizeof (arr) / sizeof (arr[0]);
  
     reverse(arr, n, k);
  
     for ( int i = 0; i < n; i++)
         cout << arr[i] << " " ;
  
     return 0;
}

Java

// Java program to reverse every sub-array formed by
// consecutive k elements
class GFG {
      
     // Function to reverse every sub-array formed by
     // consecutive k elements
     static void reverse( int arr[], int n, int k)
     {
         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 ;
             }
         }
     }
      
     // Driver method
     public static void main(String[] args)
     {
          
         int arr[] = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 };
         int k = 3 ;
      
         int n = arr.length;
      
         reverse(arr, n, k);
      
         for ( int i = 0 ; i < n; i++)
             System.out.print(arr[i] + " " );
     }
}
  
// This code is contributed by Anant Agarwal.

Python3

# Python 3 program to reverse every 
# sub-array formed by consecutive k
# elements
  
# Function to reverse every sub-array
# formed by consecutive k elements
def reverse(arr, n, k):
     i = 0
      
     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
      
# Driver code
arr = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ] 
  
k = 3
n = len (arr) 
reverse(arr, n, k)
  
for i in range ( 0 , n):
         print (arr[i], end = " " )
          
# This code is contributed by Smitha Dinesh Semwal

C#

// C# program to reverse every sub-array 
// formed by consecutive k elements
using System;
  
class GFG
{
  
// Function to reverse every sub-array 
// formed by consecutive k elements
public static void reverse( int [] arr, int n, int k)
{
     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;
         }
     }
}
  
// Driver Code
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;
  
     reverse(arr, n, k);
  
     for ( int i = 0; i < n; i++)
     {
         Console.Write(arr[i] + " " );
     }
}
}
  
// This code is contributed 
// by Shrikant13

的PHP

<?php
// PHP program to reverse every sub-array 
// formed by consecutive k elements
      
// Function to reverse every sub-array 
// formed by consecutive k elements
function reverse( $arr , $n , $k )
{
     for ( $i = 0; $i < $n ; $i += $k )
     {
         $left = $i ;
  
         // to handle case when k is not 
         // multiple of n
         $right = min( $i + $k - 1, $n - 1);
         $temp ;
          
         // reverse the sub-array [left, right]
         while ( $left < $right )
         {
             $temp = $arr [ $left ];
             $arr [ $left ] = $arr [ $right ];
             $arr [ $right ] = $temp ;
             $left += 1;
             $right -= 1;
         }
     }
     return $arr ;
}
  
// Driver Code
$arr = array (1, 2, 3, 4, 5, 6, 7, 8);
$k = 3;
  
$n = sizeof( $arr );
  
$arr1 = reverse( $arr , $n , $k );
  
for ( $i = 0; $i < $n ; $i ++)
     echo $arr1 [ $i ] . " " ;
  
// This code is contributed 
// by Akanksha Rai
?>

输出如下：

3 2 1 6 5 4 8 7

时间复杂度

上述解决方案的值为O(n)。

辅助空间

该程序使用的是O(1)。

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。