Array 为这个归并排序函数提供了正确的输出,但 vector 给出了不正确的输出.出了什么问题? [英] Array gives correct output for this mergesort function but vector is giving incorrect output. What is going wrong?
问题描述
过去 2-3 天我一直在尝试使用归并排序来解决计数反转问题,经过多次尝试,我刚刚从 Hackerrank 的社论中找到了答案,现在他们的代码正在使用 Array
,如果我使用 Vector
而不是 Array
,答案是 Actual answer + 1
(或者说不同的避风港在很多情况下都没有尝试过).我想知道可能是什么原因.
I've been trying to do the count inversions question using mergesort for the past 2-3 days and after much trying, I just picked up the answer from Hackerrank's editorial, now their code is using an Array
, and if I use a Vector
instead of an Array
, the answer is Actual answer + 1
(or different to say the least haven't tried it on many cases). I was wondering what might be the reason for it.
关于这段代码的解释,我还有另一个问题,特别是变量声明及其在 mergei 函数中的使用.我从概念上理解其余的代码,但因为这部分,我有些困惑.
I also have another question on explanation of this code, in particular the variable declarations and their use in the mergei function. I understand the rest of the code conceptually, but because of this part, I have some confusion.
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,这在数组的情况下我不必担心.
I was not passing the Vector by reference, something I didn't have to worry about in case of array.
这篇关于Array 为这个归并排序函数提供了正确的输出,但 vector 给出了不正确的输出.出了什么问题?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!