java - 需要帮助计算合并排序的反转

Question

以下代码计算数组 nums 中的倒置次数(对 i,j 使得 j>i && nums[i] > nums[j] )通过归并排序。

是否可以使用相同的方法来计算特殊反转的数量，如 j>i && nums[i] > 2*nums[j] ？

我该如何修改这段代码？

public static void main (String args[])
{
    int[] nums = {9, 16, 1, 2, 3, 4, 5, 6};
    System.out.println("Strong Inversions: " + countInv(nums));         
}

public static int countInv(int nums[])
{  
    int mid = nums.length/2;
    int countL, countR, countMerge;

    if(nums.length <= 1)
    {
        return 0;
    }

    int left[] = new int[mid];
    int right[] = new int[nums.length - mid];

    for(int i = 0; i < mid; i++)
    {
        left[i] = nums[i];
    }

    for(int i = 0; i < nums.length - mid; i++)
    {
        right[i] = nums[mid+i];
    }

    countL = countInv (left);
    countR = countInv (right);

    int mergedResult[] = new int[nums.length];
    countMerge = mergeCount (left, right, mergedResult);

    for(int i = 0; i < nums.length; i++)
    {
        nums[i] = mergedResult[i];
    }

    return (countL + countR + countMerge);
}


public static int mergeCount (int left[], int right[], int merged[])
{
    int a = 0, b = 0, counter = 0, index=0;

    while ( ( a < left.length) && (b < right.length) )
    {
        if(left[a] <= right[b])
        {
            merged [index] = left[a++];
        }
        else 
        {   
            merged [index] = right[b++];
            counter += left.length - a;
        }
        index++;
    }

    if(a == left.length)
    {
        for (int i = b; i < right.length; i++)
        {
            merged [index++] = right[i];
        }
    }
    else
    {
        for (int i = a; i < left.length; i++)
        {
            merged [index++] = left[i];
        }
    }
    return counter;
} 

我试过了

while ((a < left.length) && (b < right.length)) {
    if (left[a] <= right[b]) {
        merged[index] = left[a++];
    } else {
        if (left[a] > 2 * right[b]) {
            counter += left.length - a;
        }
        merged[index] = right[b++];
    }
    index++;
}

但是当 left[a]<2*right[b] 时 while 循环中有一个错误但是left[a+n] maybe>2*right[b] , 例如左数组是 {9,16}右数组是{5,6} , 9<2*5 但 16>2*5。我的代码只是跳过了这样的情况，结果数量少于应有的数量

Answer 1

mergeCount 中的 while 循环有两个功能:将 left 和 right 合并到 merged，并计算 left–right 反转的次数。对于特殊的反转，最简单的方法是将循环分成两部分，先计算反转，然后合并。计数反转的新触发器是 left[a] > 2*right[b]。

之所以有两个循环是因为计数特殊反转需要合并left和2*right，排序需要合并left 正确。可能在一个循环中使用三个不同的索引，但逻辑会更复杂。