c*********i
发帖数: 46 | 1 http://www.geeksforgeeks.org/counting-inversions/
给出了代码，可是看了程序后， 有点不解，想请大牛指教一下：
/*this is tricky -- see above explanation/diagram for merge()*/
inv_count = inv_count + (mid - i);
不应该是：
inv_count = inv_count + (mid - i)+1？
当copy a[j]时，left array 剩下的都是inversion,不应该是（mid - i）+ 1 个吗？
int merge(int arr[], int temp[], int left, int mid, int right)
{
int i, j, k;
int inv_count = 0;
i = left; /* i is index for left subarray*/
j = mid; /* i is index for right subarray*/
k = left; /* i is index for resultant merged subarray*/
while ((i <= mid - 1) && (j <= right))
{
if (arr[i] <= arr[j])
{
temp[k++] = arr[i++];
}
else
{
temp[k++] = arr[j++];
/*this is tricky -- see above explanation/diagram for merge()*/
inv_count = inv_count + (mid - i);
}
}
/* Copy the remaining elements of left subarray
(if there are any) to temp*/
while (i <= mid - 1)
temp[k++] = arr[i++];
/* Copy the remaining elements of right subarray
(if there are any) to temp*/
while (j <= right)
temp[k++] = arr[j++];
/*Copy back the merged elements to original array*/
for (i=left; i <= right; i++)
arr[i] = temp[i];
return inv_count;
} | b******7
发帖数: 92 | 2 int merge(int arr[], int temp[], int left, int mid, int right)
{
int count = 0;
int i = left, j = mid, k= 0;
while(i < mid && j <= right){
if(arr[i] <= arr[j]){
temp[k++] = arr[i++];
count += j - mid;
}else{
temp[k++] = arr[j++];
}
}
while(i < mid){
temp[k++] = arr[i++];
count += j - mid;
}
while(j <= right){
temp[k++] = arr[j++];
}
for(int i = left; i <= right; i++){
arr[i] = temp[i-left];
}
return count;
} | r********d
发帖数: 7742 | 3 是mid-i还是mid-i＋1取决于你把mid放到左边还是右边。左边就加一，右边就不加。
【在 c*********i 的大作中提到】
: http://www.geeksforgeeks.org/counting-inversions/
: 给出了代码，可是看了程序后， 有点不解，想请大牛指教一下：
: /*this is tricky -- see above explanation/diagram for merge()*/
: inv_count = inv_count + (mid - i);
: 不应该是：
: inv_count = inv_count + (mid - i)+1？
: 当copy a[j]时，left array 剩下的都是inversion,不应该是（mid - i）+ 1 个吗？
: int merge(int arr[], int temp[], int left, int mid, int right)
: {
: int i, j, k;
|
|
