我把A[0..n − 1]
设计成n个实数的数组。
如果一对(Ai,Aj )是乱序的,即i Aj,则称这些数是逆的。用于计算倒置次数的O(n log n)
算法。
我正在尝试获取倒置的数量,但我不知道我的代码有什么问题,我认为排序方法有问题。
class Q2
{
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
static int merge(int arr[], int l, int m, int r)
{
// Find sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;
int counter =0;
/* Create temp arrays */
int L[] = new int [n1];
int R[] = new int [n2];
/*Copy data to temp arrays*/
for (int i=0; i<n1; ++i)
L[i] = arr[l + i];
for (int j=0; j<n2; ++j)
R[j] = arr[m + 1+ j];
/* Merge the temp arrays */
// Initial indexes of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarry array
int k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
counter = counter + (m - i);
}
k++;
}
/* Copy remaining elements of L[] if any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy remaining elements of R[] if any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
return counter ;
}
// Main function that sorts arr[l..r] using
// merge()
static int sort(int arr[], int l, int r)
{
int counter=0;
if (l < r)
{
// Find the middle point
int m = (l+r)/2;
// count first and second halves
counter=sort(arr, l, m);
counter+=sort(arr , m+1, r);
// count two halves
counter+= merge(arr, l, m, r);
}
return counter;
}
// Driver method
public static void main(String args[])
{
int arr[] = {2, 4, 1, 3,5};
System.out.println("Number of inversions are " + sort(arr, 0,arr.length-1 ) );
}
}
发布于 2018-10-09 04:08:37
你的方法有一个根本性的缺陷。这个
counter = counter + (m - i)
假设m之前的所有元素都小于R中的值,这是不正确的。请记住,m之前的大部分数组可能已经排序。
counter = counter + (m - l - i)
可能更正确,但在这种情况下,您可能仍然会计算双倍。请注意,当它们不在原始数组中的原始位置时,需要对它们进行计数。
发布于 2018-10-09 18:46:37
你得换掉
counter = counter + (m - i)
使用
counter = counter + (n1 - i)
插图:假设一个左数组L的数字为1,6,8,9,一个右数组R的数字为4,5,7。下面显示了循环中单个递归步骤的迭代:
通常,您可以通过以不同的顺序执行反转来对数组进行排序。但是,排序所需的最小倒数是明确的,因此与该顺序无关。由于该算法使用这些可选序列之一,因此它提供了明确的最小数量的反转。这特别意味着没有倒置被计算两次或省略。
该算法为您的数组{2,4,1,3,5}提供了总共3次反转的最小数量:(4,1),(4,3)和(2,1)。
https://stackoverflow.com/questions/52708036
复制相似问题