C++程序 将数组拆分并将第一部分添加到结尾-2
给定一个数组并从指定位置开始拆分它,然后将数组的第一部分移动到结尾。
例子:
输入 : arr[] = {12, 10, 5, 6, 52, 36}
k = 2
输出 : arr[] = {5, 6, 52, 36, 12, 10}
解释 : 从索引2开始拆分,将第一部分{12, 10}添加到末尾。
输入 : arr[] = {3, 1, 2}
k = 1
输出 : arr[] = {1, 2, 3}
解释 : 从索引1开始拆分,将第一部分添加到末尾。
这里讨论了一个O(n * k)的解决方案。可以使用下面讨论的反转算法以O(n)时间解决此问题。
1. 将数组从0到n-1反转(其中n为数组的大小)。
2. 将数组从0到n-k-1反转。
3. 将数组从n-k到n-1反转。
//C++程序,将数组拆分并将第一部分添加到结尾
#include <bits/stdc++.h>
using namespace std;
/*函数以从start到end的索引来反转arr[]*/
void rvereseArray(int arr[], int start, int end)
{
while (start < end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
//打印数组的函数
void printArray(int arr[], int size)
{
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
}
/* 函数将大小为n的arr[]左移k个元素*/
void splitArr(int arr[], int k, int n)
{
rvereseArray(arr, 0, n - 1);
rvereseArray(arr, 0, n - k - 1);
rvereseArray(arr, n - k, n - 1);
}
/*驱动程序以测试以上函数*/
int main()
{
int arr[] = { 12, 10, 5, 6, 52, 36 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 2;
//调用函数
splitArr(arr, k, n);
printArray(arr, n);
return 0;
}
输出:
5 6 52 36 12 10