C++编程 重排数组,使得arr[i]>=arr[j](如果i是偶数),则arr[i]<=arr[j] (如果i是奇数),同时j < i
给定一个包含n个元素的数组。我们的任务是编写一个程序,将数组重排,使得偶数位置上的元素大于它之前的所有元素,而奇数位置上的元素小于它之前的所有元素。
例子:
Input : arr[] = {1, 2, 3, 4, 5, 6, 7}
Output : 4 5 3 6 2 7 1
Input : arr[] = {1, 2, 1, 4, 5, 6, 8, 8}
Output : 4 5 2 6 1 8 1 8
解决这个问题的思路是先创建原始数组的辅助副本,然后对复制的数组进行排序。现在,具有n个元素的数组中的偶数位置总数是floor(n/2),剩余的是奇数位置的数量。现在,按以下方式使用排序的数组向原始数组填充奇数和偶数位置:
- 总的奇数位置将是n – floor(n/2)。从排序数组的(n – floor(n/2))个位置开始,并将元素复制到排序数组的第一个位置。从该位置向左遍历排序数组,并继续向右填充原始数组的奇数位置。
- 从(n – floor(n/2) + 1)个位置开始向右遍历排序数组,并从第二个位置开始填充原始数组。
下面是上述思路的实现:
// C++ program to rearrange the array
// as per the given condition
#include <bits/stdc++.h>
using namespace std;
// function to rearrange the array
void rearrangeArr(int arr[], int n)
{
// total even positions
int evenPos = n / 2;
// total odd positions
int oddPos = n - evenPos;
int tempArr[n];
// copy original array in an
// auxiliary array
for (int i = 0; i < n; i++)
tempArr[i] = arr[i];
// sort the auxiliary array
sort(tempArr, tempArr + n);
int j = oddPos - 1;
// fill up odd position in original
// array
for (int i = 0; i < n; i += 2) {
arr[i] = tempArr[j];
j--;
}
j = oddPos;
// fill up even positions in original
// array
for (int i = 1; i < n; i += 2) {
arr[i] = tempArr[j];
j++;
}
// display array
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
// Driver code
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
int size = sizeof(arr) / sizeof(arr[0]);
rearrangeArr(arr, size);
return 0;
}
输出:
4 5 3 6 2 7 1
时间复杂度: O(N*logN),因为我们使用了一个排序函数。
空间复杂度: O(N),因为我们使用了额外的空间。