Sto navigando su una sfida online di codifica online e sono stato colpito da qualche parte. Obiettivo del programma è trovare il numero massimo di swap richiesto nell'ordinamento di un array tramite l'ordinamento per inserzione in tempo efficiente
il primo approccio che è l'approccio a forza bruta dà la complessità di O (n ^ 2)
Il prossimo che posso pensare è un algoritmo di merge sort il codice che uso per questo è
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int mergesort(int *,int);
int _mergesort(int *,int *,int,int);
int merge(int *,int *,int,int,int);
int mergesort(int arr[],int n)
{
int temp[n];
return _mergesort(arr,temp,0,n-1);
}
int _mergesort(int arr[],int temp[],int left,int right)
{
int mid,count=0;
if(right>left)
{
mid=(left+right)/2;
count=_mergesort(arr,temp,left,mid);
count+=_mergesort(arr,temp,mid+1,right);
count+=merge(arr,temp,left,mid+1,right);
}
return count;
}
int merge(int arr[],int temp[],int left,int mid,int right)
{
int i, j, k;
int count = 0;
i = left;
j = mid;
k = left;
while ((i <= mid - 1) && (j <= right))
{
if (arr[i] <= arr[j])
{
temp[k++] = arr[i++];
}
else
{
temp[k++] = arr[j++];
count = count + (mid - i);
}
}
while (i <= mid - 1)
temp[k++] = arr[i++];
while (j <= right)
temp[k++] = arr[j++];
for (i=left; i <= right; i++)
arr[i] = temp[i];
return count;
}
int main()
{
int n,tc,i;
cin>>tc;
while(tc)
{
cin>>n;
int arr[n];
for(i=0;i<n;i++)
cin>>arr[i];
cout<<mergesort(arr,n);
tc--;
}
return 0;
}
The example test case is
Sample Input:
2
5
1 1 1 2 2
5
2 1 3 1 2
Sample Output:
0
4
questo mi dà una complessità di nlogn Inizialmente il programma legge il numero di test case che è 2 e seguito da due test case
l'algoritmo funziona bene per un piccolo intervallo di valori ma mostra il limite di tempo superato errore in alcuni casi di test.
Qual è il modo più efficace per farlo, non posso trovare alcun suggerimento o le modifiche sarebbero apprezzate.
