这两三天我一直在尝试用mergesort做计数反转题,经过反复尝试,我才从Hackerrank的小编那里得到了答案,现在他们的代码是用一个 Array
如果我使用 Vector
而非 Array
答案是 Actual answer + 1
(或者说不一样至少没有在很多情况下试过)。我想知道这可能是什么原因。
我还有一个问题是关于这段代码的解释,特别是变量声明和它们在mergei函数中的使用。我从概念上理解了代码的其余部分,但是因为这部分,我有一些困惑。
int ni = ((i+j)/2) + 1, nj = j + 1;
int s = i;
int* arr = new int [j - i + 1];
j = ni; int k = 0;
代码。
void mergei(int a[], int i, int j) {
int ni = ((i+j)/2) + 1, nj = j + 1;
int s = i;
int* arr = new int [j - i + 1];
j = ni; int k = 0;
while(i < ni && j < nj) {
if(a[i] <= a[j]) {
arr[k++] = a[i++];
} else {
arr[k++] = a[j++];
ans += (ni-i);
}
}
for(; i < ni; i++, k++) arr[k] = a[i];
for(; j < nj; j++, k++) arr[k] = a[j];
for(k = 0; s < nj; s++, k++) a[s] = arr[k];
delete [] arr;
}
void m_sort(int a[], int i, int j) {
if(i < j) {
m_sort(a, i, (i+j)/2);
m_sort(a, ((i+j)/2) + 1, j);
mergei(a, i, j);
}
}
int main() {
// vector<int> a = {2, 1, 3, 1, 2};
int a[] = {2, 1, 3, 1, 2};
// int n = a.size();
int n = sizeof(a)/sizeof(a[0]);
m_sort(a, 0, n - 1);
cout << ans << endl;
return 0;
}
我是没有通过引用来传递Vector的,这一点在数组的情况下我不用担心。