过去2-3天，我一直在尝试使用mergesort进行计数反转问题，经过大量尝试，我刚刚从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.
更多推荐
如果我在计算Inversions时使用Vector而不是Array,会有不同的答案,这可能是什么原因?
发布评论