我得到了 this编程“类(class)”中的挑战。最终我决定采用“二叉索引树”解决方案,因为数据结构是我想了解更多的东西。实现 BIT 有点直接,之后的事情 - 不是那么多。我在将解决方案上传到服务器时遇到了“Fatal Signal 11”,据我所知,这有点类似于 Null 指针异常。想不通问题,决定查看other BIT 的解决方案,但偶然发现了同样的问题。
#include<iostream>
using namespace std;
/* <BLACK MAGIC COPIED FROM geeksforgeeks.org> */
int getSum(int BITree[], int index){
int sum = 0;
while (index > 0){
sum += BITree[index];
index -= index & (-index);
}
return sum;
}
void updateBIT(int BITree[], int n, int index, int val){
while (index <= n){
BITree[index] += val;
index += index & (-index);
}
}
/* <BLACK MAGIC COPIED FROM geeksforgeeks.org> */
int Count(int arr[], int x){
int sum = 0;
int biggest = 0;
for (int i=0; i<x; i++) {
if (biggest < arr[i]) biggest = arr[i];
}
int bit[biggest+1];
for (int i=1; i<=biggest; i++) bit[i] = 0;
for (int i=x-1; i>=0; i--)
{
sum += getSum(bit, arr[i]-1);
updateBIT(bit, biggest, arr[i], 1);
}
return sum;
}
int main(){
int x;
cin >> x;
int *arr = new int[x];
for (int temp = 0; temp < x; temp++) cin >> arr[temp];
/*sizeof(arr) / sizeof(arr[0]); <-- someone suggested this,
but it doesn't change anything from what I can tell*/
cout << Count(arr,x);
delete [] arr;
return 0;
}
我对此很困惑。这可能只是我遗漏的一些简单的事情,但我真的不知道。非常感谢任何帮助!
最佳答案
你的条件是每个数字都在 1 到 1018 之间。因此,您的最大数字可以是 1018。这对于以下行来说太多了:
int bit[biggest+1];
关于C++ 计数数组中的反转,致命信号 11 (BIT),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53781865/