给定一个正整数数组A[1...N],您必须按以下方式按升序对其进行排序:在每个操作中,选择任意 2 个不重叠的等长子数组并交换它们。即,选择两个子数组 A[i...(i+k-1)] 和 A[j...(j+k-1)]这样 i+k-1< j 并且将 A[i] 与 A[j] 交换,A[i+1] 与 < strong>A[j+1] ... 和 A[i+k-1] 与 A[j+k-1]。
Example:
For N=6
6 7 8 1 2 3
Only one operation is needed as after swapping (6 7 8) and (1 2 3 ) sub arrays
we can get 1 2 3 6 7 8 , that is sorted.
我们如何才能以最有效的方式计算出最少的交换次数? 来源: https://www.hackerearth.com/problem/approximate/swap-and-sort/
最佳答案
#include <iostream>
using namespace std;
void swaparr(int a[],int l,int r,int n) {
for(int i=l,j=r;i<=l+n&&j<=r+n;i++,j++)
swap(a[i],a[j]);
}
int findMax(int a[],int n) {
int index = 0;
for(int i=1;i<=n;i++)
if(a[i] > a[index])
index = i;
return index;
}
void sort(int a[],int n) {
for(int r=n-1;r>;0;r--) {
int index = findMax(a,r);
if(index != r) {
int l = min(r-index-1,index);
swaparr(a,index-l,r-l,l);
}
}
}
int main() {
int a[] = {7,23,8,234,3,6,41,334};
int n = 8;
sort(a,n);
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
return 0;
}
逻辑:在每个操作中找到最大元素并执行交换以使最大元素到达末尾。 执行此操作 N 次,每次将数组大小减少一个,并力求在每次操作中拥有最大元素。 不需要进行 N 次交换。它仅在最大元素不在其位置时才执行交换。 T = O(n2)
关于arrays - 如果可以交换两个大小相等的子数组,则对数组进行排序的交换操作的最小数量,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28741575/