本文概述
有一个给定的数组, 并将其从指定位置拆分, 然后将数组add的第一部分移至末尾。
例子:
Input : arr[] = {12, 10, 5, 6, 52, 36}
k = 2
Output : arr[] = {5, 6, 52, 36, 12, 10}
Explanation : Split from index 2 and first
part {12, 10} add to the end .
Input : arr[] = {3, 1, 2}
k = 1
Output : arr[] = {1, 2, 3}
Explanation : Split from index 1 and first
part add to the end.
推荐:请尝试以下方法{IDE}首先, 在继续解决方案之前。
简单的解决方案
我们一一旋转数组。
C ++
// CPP program to split array and move first
// part to end.
#include <bits/stdc++.h>
using namespace std;
void splitArr( int arr[], int n, int k)
{
for ( int i = 0; i < k; i++) {
// Rotate array by 1.
int x = arr[0];
for ( int j = 0; j < n - 1; ++j)
arr[j] = arr[j + 1];
arr[n - 1] = x;
}
}
// Driver code
int main()
{
int arr[] = { 12, 10, 5, 6, 52, 36 };
int n = sizeof (arr) / sizeof (arr[0]);
int position = 2;
splitArr(arr, 6, position);
for ( int i = 0; i < n; ++i)
printf ( "%d " , arr[i]);
return 0;
}
Java
// Java program to split array and move first
// part to end.
import java.util.*;
import java.lang.*;
class GFG {
public static void splitArr( int arr[], int n, int k)
{
for ( int i = 0 ; i < k; i++) {
// Rotate array by 1.
int x = arr[ 0 ];
for ( int j = 0 ; j < n - 1 ; ++j)
arr[j] = arr[j + 1 ];
arr[n - 1 ] = x;
}
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 12 , 10 , 5 , 6 , 52 , 36 };
int n = arr.length;
int position = 2 ;
splitArr(arr, 6 , position);
for ( int i = 0 ; i < n; ++i)
System.out.print(arr[i] + " " );
}
}
// Code Contributed by Mohit Gupta_OMG <(0_o)>
Python3
# Python program to split array and move first
# part to end.
def splitArr(arr, n, k):
for i in range ( 0 , k):
x = arr[ 0 ]
for j in range ( 0 , n - 1 ):
arr[j] = arr[j + 1 ]
arr[n - 1 ] = x
# main
arr = [ 12 , 10 , 5 , 6 , 52 , 36 ]
n = len (arr)
position = 2
splitArr(arr, n, position)
for i in range ( 0 , n):
print (arr[i], end = ' ' )
# Code Contributed by Mohit Gupta_OMG <(0_o)>
C#
// C# program to split array
// and move first part to end.
using System;
class GFG {
// Function to spilt array and
// move first part to end
public static void splitArr( int [] arr, int n, int k)
{
for ( int i = 0; i < k; i++)
{
// Rotate array by 1.
int x = arr[0];
for ( int j = 0; j < n - 1; ++j)
arr[j] = arr[j + 1];
arr[n - 1] = x;
}
}
// Driver code
public static void Main()
{
int [] arr = {12, 10, 5, 6, 52, 36};
int n = arr.Length;
int position = 2;
splitArr(arr, 6, position);
for ( int i = 0; i < n; ++i)
Console.Write(arr[i] + " " );
}
}
// This code is contributed by Shrikant13.
的PHP
<?php
// PHP program to split array
// and move first part to end.
function splitArr(& $arr , $n , $k )
{
for ( $i = 0; $i < $k ; $i ++)
{
// Rotate array by 1.
$x = $arr [0];
for ( $j = 0; $j < $n - 1; ++ $j )
$arr [ $j ] = $arr [ $j + 1];
$arr [ $n - 1] = $x ;
}
}
// Driver code
$arr = array (12, 10, 5, 6, 52, 36);
$n = sizeof( $arr );
$position = 2;
splitArr( $arr , 6, $position );
for ( $i = 0; $i < $n ; ++ $i )
echo $arr [ $i ]. " " ;
// This code is contributed
// by ChitraNayal
?>
输出如下:
5 6 52 36 12 10
上述解决方案的时间复杂度为O(nk)。
另一种方法:
另一种方法是制作一个具有两倍大小的临时数组, 然后将数组元素复制到新数组两次。然后, 以旋转为起始索引, 将元素从新数组复制到我们的数组, 直到数组的长度。
下面是上述方法的实现。
C ++
// CPP program to split array and move first
// part to end.
#include <bits/stdc++.h>
using namespace std;
// Function to spilt array and
// move first part to end
void splitArr( int arr[], int length, int rotation)
{
int tmp[length * 2] = {0};
for ( int i = 0; i < length; i++)
{
tmp[i] = arr[i];
tmp[i + length] = arr[i];
}
for ( int i = rotation; i < rotation + length; i++)
{
arr[i - rotation] = tmp[i];
}
}
// Driver code
int main()
{
int arr[] = { 12, 10, 5, 6, 52, 36 };
int n = sizeof (arr) / sizeof (arr[0]);
int position = 2;
splitArr(arr, n, position);
for ( int i = 0; i < n; ++i)
printf ( "%d " , arr[i]);
return 0;
}
// This code is contributed by YashKhandelwal8
Java
// Java program to split array and move first
// part to end.
import java.util.*;
import java.lang.*;
class GFG {
// Function to spilt array and
// move first part to end
public static void SplitAndAdd( int [] A, int length, int rotation){
//make a temporary array with double the size
int [] tmp = new int [length* 2 ];
// copy array element in to new array twice
System.arraycopy(A, 0 , tmp, 0 , length);
System.arraycopy(A, 0 , tmp, length, length);
for ( int i=rotation;i<rotation+length;i++)
A[i-rotation]=tmp[i];
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 12 , 10 , 5 , 6 , 52 , 36 };
int n = arr.length;
int position = 2 ;
SplitAndAdd(arr, n, position);
for ( int i = 0 ; i < n; ++i)
System.out.print(arr[i] + " " );
}
}
Python3
# Python3 program to split array and
# move first part to end.
# Function to spilt array and
# move first part to end
def SplitAndAdd(A, length, rotation):
# make a temporary array with double
# the size and each index is initialized to 0
tmp = [ 0 for i in range (length * 2 )]
# copy array element in to new array twice
for i in range (length):
tmp[i] = A[i]
tmp[i + length] = A[i]
for i in range (rotation, rotation + length, 1 ):
A[i - rotation] = tmp[i];
# Driver code
arr = [ 12 , 10 , 5 , 6 , 52 , 36 ]
n = len (arr)
position = 2
SplitAndAdd(arr, n, position);
for i in range (n):
print (arr[i], end = " " )
print ()
# This code is contributed by SOUMYA SEN
C#
// C# program to split array
// and move first part to end.
using System;
class GFG
{
// Function to spilt array and
// move first part to end
public static void SplitAndAdd( int [] A, int length, int rotation)
{
// make a temporary array with double the size
int [] tmp = new int [length * 2];
// copy array element in to new array twice
Array.Copy(A, 0, tmp, 0, length);
Array.Copy(A, 0, tmp, length, length);
for ( int i = rotation; i < rotation + length; i++)
{
A[i - rotation] = tmp[i];
}
}
// Driver code
public static void Main( string [] args)
{
int [] arr = new int [] {12, 10, 5, 6, 52, 36};
int n = arr.Length;
int position = 2;
SplitAndAdd(arr, n, position);
for ( int i = 0; i < n; ++i)
{
Console.Write(arr[i] + " " );
}
}
}
// This code is contributed by kumar65
输出如下:
5 6 52 36 12 10
以下文章讨论了一种有效的O(n)解决方案:拆分数组并将第一部分添加到末尾|套装2
这个问题只不过是数组旋转问题, 我们可以在此处应用优化的O(n)数组旋转方法。
数组旋转程序
阵列旋转的块交换算法
阵列旋转的逆向算法
快速找到数组的多个左旋转|套装1
在O(n)时间和O(1)空间中打印数组的左旋转
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。