[合集] 宝宝会爬以后，家里脏脏的地毯怎么办？# NextGeneration - 我爱宝宝
c*i
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;
}
给出了代码，可是看了程序后， 有点不解，想请大牛指教一下：
/*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;
}
