高级算法设计：数组旋转程序

2021年3月16日15:36:45 发表评论 906 次浏览

本文概述

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

写一个rotate(ar[]， d, n)函数，旋转大小为n个元素的数组arr[]。

将上面的数组旋转2将使数组变成：

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

方法1(使用临时数组)

Input arr[] = [1, 2, 3, 4, 5, 6, 7], d = 2, n =7
1) Store the first d elements in a temp array
   temp[] = [1, 2]
2) Shift rest of the arr[]
   arr[] = [3, 4, 5, 6, 7, 6, 7]
3) Store back the d elements
   arr[] = [3, 4, 5, 6, 7, 1, 2]

时间复杂度：

O(n)

辅助空间：

O(d)

方法2(一一旋转)

leftRotate(arr[], d, n)
start
  For i = 0 to i < d
    Left rotate all elements of arr[] by one
end

要旋转一个, 将arr [0]存储在临时变量temp中, 将arr [1]移至arr [0], 将arr [2]移至arr [1]…最后将temp移至arr [n-1]

让我们以相同的示例arr [] = [1、2、3、4、5、6、7], d = 2

将arr []旋转1倍

第一次旋转后得到[2, 3, 4, 5, 5, 6, 7, 1], 第二次旋转后得到[3, 4, 5, 6, 7, 1, 2]。

下面是上述方法的实现：

C ++

// C++ program to rotate an array by
// d elements
#include <bits/stdc++.h>
using namespace std;
  
/*Function to left Rotate arr[] of 
   size n by 1*/
void leftRotatebyOne( int arr[], int n)
{
     int temp = arr[0], i;
     for (i = 0; i < n - 1; i++)
         arr[i] = arr[i + 1];
  
     arr[i] = temp;
}
  
/*Function to left rotate arr[] of size n by d*/
void leftRotate( int arr[], int d, int n)
{
     for ( int i = 0; i < d; i++)
         leftRotatebyOne(arr, n);
}
  
/* utility function to print an array */
void printArray( int arr[], int n)
{
     for ( int i = 0; i < n; i++)
         cout << arr[i] << " " ;
}
  
/* Driver program to test above functions */
int main()
{
     int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
     int n = sizeof (arr) / sizeof (arr[0]);
  
     // Function calling
     leftRotate(arr, 2, n);
     printArray(arr, n);
  
     return 0;
}

C

// C program to rotate an array by
// d elements
#include <stdio.h>
  
/* Function to left Rotate arr[] of size n by 1*/
void leftRotatebyOne( int arr[], int n);
  
/*Function to left rotate arr[] of size n by d*/
void leftRotate( int arr[], int d, int n)
{
     int i;
     for (i = 0; i < d; i++)
         leftRotatebyOne(arr, n);
}
  
void leftRotatebyOne( int arr[], int n)
{
     int temp = arr[0], i;
     for (i = 0; i < n - 1; i++)
         arr[i] = arr[i + 1];
     arr[i] = temp;
}
  
/* utility function to print an array */
void printArray( int arr[], int n)
{
     int i;
     for (i = 0; i < n; i++)
         printf ( "%d " , arr[i]);
}
  
/* Driver program to test above functions */
int main()
{
     int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
     leftRotate(arr, 2, 7);
     printArray(arr, 7);
     return 0;
}

Java

// Java program to rotate an array by
// d elements
  
class RotateArray {
     /*Function to left rotate arr[] of size n by d*/
     void leftRotate( int arr[], int d, int n)
     {
         for ( int i = 0 ; i < d; i++)
             leftRotatebyOne(arr, n);
     }
  
     void leftRotatebyOne( int arr[], int n)
     {
         int i, temp;
         temp = arr[ 0 ];
         for (i = 0 ; i < n - 1 ; i++)
             arr[i] = arr[i + 1 ];
         arr[i] = temp;
     }
  
     /* utility function to print an array */
     void printArray( int arr[], int n)
     {
         for ( int i = 0 ; i < n; i++)
             System.out.print(arr[i] + " " );
     }
  
     // Driver program to test above functions
     public static void main(String[] args)
     {
         RotateArray rotate = new RotateArray();
         int arr[] = { 1 , 2 , 3 , 4 , 5 , 6 , 7 };
         rotate.leftRotate(arr, 2 , 7 );
         rotate.printArray(arr, 7 );
     }
}
  
// This code has been contributed by Mayank Jaiswal

Python3

# Python3 program to rotate an array by 
# d elements 
# Function to left rotate arr[] of size n by d*/
def leftRotate(arr, d, n):
     for i in range (d):
         leftRotatebyOne(arr, n)
  
# Function to left Rotate arr[] of size n by 1*/ 
def leftRotatebyOne(arr, n):
     temp = arr[ 0 ]
     for i in range (n - 1 ):
         arr[i] = arr[i + 1 ]
     arr[n - 1 ] = temp
          
  
# utility function to print an array */
def printArray(arr, size):
     for i in range (size):
         print ( "% d" % arr[i], end = " " )
  
   
# Driver program to test above functions */
arr = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 ]
leftRotate(arr, 2 , 7 )
printArray(arr, 7 )
  
# This code is contributed by Shreyanshi Arun

C#

// C# program for array rotation
using System;
  
class GFG {
     /* Function to left rotate arr[]
     of size n by d*/
     static void leftRotate( int [] arr, int d, int n)
     {
         for ( int i = 0; i < d; i++)
             leftRotatebyOne(arr, n);
     }
  
     static void leftRotatebyOne( int [] arr, int n)
     {
         int i, temp = arr[0];
         for (i = 0; i < n - 1; i++)
             arr[i] = arr[i + 1];
  
         arr[i] = temp;
     }
  
     /* utility function to print an array */
     static void printArray( int [] arr, int size)
     {
         for ( int i = 0; i < size; i++)
             Console.Write(arr[i] + " " );
     }
  
     // Driver code
     public static void Main()
     {
         int [] arr = { 1, 2, 3, 4, 5, 6, 7 };
         leftRotate(arr, 2, 7);
         printArray(arr, 7);
     }
}
  
// This code is contributed by Sam007

的PHP

<?php 
// PHP program to rotate an array
// by d elements
  
/*Function to left Rotate arr[]  
of size n by 1*/
function leftRotatebyOne(& $arr , $n )
{
     $temp = $arr [0];
     for ( $i = 0; $i < $n - 1; $i ++)
         $arr [ $i ] = $arr [ $i + 1];
  
     $arr [ $i ] = $temp ;
}
  
/*Function to left rotate arr[] 
   of size n by d*/
function leftRotate(& $arr , $d , $n )
{
     for ( $i = 0; $i < $d ; $i ++)
         leftRotatebyOne( $arr , $n );
}
  
/* utility function to print 
    an array */
function printArray(& $arr , $n )
{
     for ( $i = 0; $i < $n ; $i ++)
         echo $arr [ $i ] . " " ;
}
  
// Driver Code
$arr = array ( 1, 2, 3, 4, 5, 6, 7 );
$n = sizeof( $arr );
  
// Function calling
leftRotate( $arr , 2, $n );
printArray( $arr , $n );
  
// This code is contributed
// by ChitraNayal
?>

输出：

3 4 5 6 7 1 2

时间复杂度：

O(n * d)

辅助空间：

O(1)

方法3(一种杂耍算法)

这是方法2的扩展。不要将数组一一移动, 而是将数组分成不同的集合

其中集合数等于n和d的GCD并在集合内移动元素。

如果对于上面的示例数组(n = 7和d = 2), GCD为1, 则元素将仅在一组内移动, 我们仅从temp = arr [0]开始并继续移动arr [I + d]到arr [I], 最后将温度存储在正确的位置。

这是n = 12且d = 3的示例。GCD为3且

Let arr[] be {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}

a) Elements are first moved in first set – (See below 
   diagram for this movement)



          arr[] after this step --> {4 2 3 7 5 6 10 8 9 1 11 12}

b)    Then in second set.
          arr[] after this step --> {4 5 3 7 8 6 10 11 9 1 2 12}

c)    Finally in third set.
          arr[] after this step --> {4 5 6 7 8 9 10 11 12 1 2 3}

下面是上述方法的实现：

C ++

// C++ program to rotate an array by
// d elements
#include <bits/stdc++.h>
using namespace std;
  
/*Fuction to get gcd of a and b*/
int gcd( int a, int b)
{
     if (b == 0)
         return a;
  
     else
         return gcd(b, a % b);
}
  
/*Function to left rotate arr[] of siz n by d*/
void leftRotate( int arr[], int d, int n)
{
     /* To handle if d >= n */
     d = d % n;
     int g_c_d = gcd(d, n);
     for ( int i = 0; i < g_c_d; i++) {
         /* move i-th values of blocks */
         int temp = arr[i];
         int j = i;
  
         while (1) {
             int k = j + d;
             if (k >= n)
                 k = k - n;
  
             if (k == i)
                 break ;
  
             arr[j] = arr[k];
             j = k;
         }
         arr[j] = temp;
     }
}
  
// Function to print an array
void printArray( int arr[], int size)
{
     for ( int i = 0; i < size; i++)
         cout << arr[i] << " " ;
}
  
/* Driver program to test above functions */
int main()
{
     int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
     int n = sizeof (arr) / sizeof (arr[0]);
  
     // Function calling
     leftRotate(arr, 2, n);
     printArray(arr, n);
  
     return 0;
}

C

// C program to rotate an array by
// d elements
#include <stdio.h>
  
/* function to print an array */
void printArray( int arr[], int size);
  
/*Fuction to get gcd of a and b*/
int gcd( int a, int b);
  
/*Function to left rotate arr[] of siz n by d*/
void leftRotate( int arr[], int d, int n)
{
     int i, j, k, temp;
     /* To handle if d >= n */
     d = d % n;
     int g_c_d = gcd(d, n);
     for (i = 0; i < g_c_d; i++) {
         /* move i-th values of blocks */
         temp = arr[i];
         j = i;
         while (1) {
             k = j + d;
             if (k >= n)
                 k = k - n;
             if (k == i)
                 break ;
             arr[j] = arr[k];
             j = k;
         }
         arr[j] = temp;
     }
}
  
/*UTILITY FUNCTIONS*/
/* function to print an array */
void printArray( int arr[], int n)
{
     int i;
     for (i = 0; i < n; i++)
         printf ( "%d " , arr[i]);
}
  
/*Fuction to get gcd of a and b*/
int gcd( int a, int b)
{
     if (b == 0)
         return a;
     else
         return gcd(b, a % b);
}
  
/* Driver program to test above functions */
int main()
{
     int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
     leftRotate(arr, 2, 7);
     printArray(arr, 7);
     getchar ();
     return 0;
}

Java

// Java program to rotate an array by
// d elements
class RotateArray {
     /*Function to left rotate arr[] of siz n by d*/
     void leftRotate( int arr[], int d, int n)
     {
         /* To handle if d >= n */
         d = d % n;
         int i, j, k, temp;
         int g_c_d = gcd(d, n);
         for (i = 0 ; i < g_c_d; i++) {
             /* move i-th values of blocks */
             temp = arr[i];
             j = i;
             while ( true ) {
                 k = j + d;
                 if (k >= n)
                     k = k - n;
                 if (k == i)
                     break ;
                 arr[j] = arr[k];
                 j = k;
             }
             arr[j] = temp;
         }
     }
  
     /*UTILITY FUNCTIONS*/
  
     /* function to print an array */
     void printArray( int arr[], int size)
     {
         int i;
         for (i = 0 ; i < size; i++)
             System.out.print(arr[i] + " " );
     }
  
     /*Fuction to get gcd of a and b*/
     int gcd( int a, int b)
     {
         if (b == 0 )
             return a;
         else
             return gcd(b, a % b);
     }
  
     // Driver program to test above functions
     public static void main(String[] args)
     {
         RotateArray rotate = new RotateArray();
         int arr[] = { 1 , 2 , 3 , 4 , 5 , 6 , 7 };
         rotate.leftRotate(arr, 2 , 7 );
         rotate.printArray(arr, 7 );
     }
}
  
// This code has been contributed by Mayank Jaiswal

Python3

# Python3 program to rotate an array by 
# d elements 
# Function to left rotate arr[] of size n by d
def leftRotate(arr, d, n):
     d = d % n
     g_c_d = gcd(d, n)
     for i in range (g_c_d):
          
         # move i-th values of blocks 
         temp = arr[i]
         j = i
         while 1 :
             k = j + d
             if k > = n:
                 k = k - n
             if k = = i:
                 break
             arr[j] = arr[k]
             j = k
         arr[j] = temp
  
# UTILITY FUNCTIONS
# function to print an array 
def printArray(arr, size):
     for i in range (size):
         print ( "% d" % arr[i], end = " " )
  
# Fuction to get gcd of a and b
def gcd(a, b):
     if b = = 0 :
         return a;
     else :
         return gcd(b, a % b)
  
# Driver program to test above functions 
arr = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 ]
n = len (arr)
d = 2
leftRotate(arr, d, n)
printArray(arr, n)
  
# This code is contributed by Shreyanshi Arun

C#

// C# program for array rotation
using System;
  
class GFG {
     /* Function to left rotate arr[] 
     of size n by d*/
     static void leftRotate( int [] arr, int d, int n)
     {
         int i, j, k, temp;
         /* To handle if d >= n */
         d = d % n;
         int g_c_d = gcd(d, n);
         for (i = 0; i < g_c_d; i++) {
             /* move i-th values of blocks */
             temp = arr[i];
             j = i;
             while ( true ) {
                 k = j + d;
                 if (k >= n)
                     k = k - n;
                 if (k == i)
                     break ;
                 arr[j] = arr[k];
                 j = k;
             }
             arr[j] = temp;
         }
     }
  
     /*UTILITY FUNCTIONS*/
     /* Function to print an array */
     static void printArray( int [] arr, int size)
     {
         for ( int i = 0; i < size; i++)
             Console.Write(arr[i] + " " );
     }
  
     /* Fuction to get gcd of a and b*/
     static int gcd( int a, int b)
     {
         if (b == 0)
             return a;
         else
             return gcd(b, a % b);
     }
  
     // Driver code
     public static void Main()
     {
         int [] arr = { 1, 2, 3, 4, 5, 6, 7 };
         leftRotate(arr, 2, 7);
         printArray(arr, 7);
     }
}
  
// This code is contributed by Sam007

输出：

3 4 5 6 7 1 2

时间复杂度：

O(n)

辅助空间：

O(1)

请参阅以下文章了解数组旋转的其他方法：

阵列旋转的块交换算法

阵列旋转的逆向算法

如果你在上述程序/算法中发现任何错误, 请发表评论。

本文概述

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

C ++

C

Java

Python3

C#

的PHP

C ++

C

Java

Python3

C#

发表评论取消回复

登录 注册 找回密码

登录注册找回密码