algorithm - 如何更改合并排序以计算数组与排序数组的距离？

Question

注意：这个问题与倒数问题不同。

数组与排序数组的距离定义为：

 dist(A)=Sumation(j-i) for any i<j that A[i]>A[j]

. 简单地说，它可以在 O(n^2) 中计算。我的问题是如何更改合并排序以计算 O(n log n) 中的距离？例如：

input: 5 2 3 4 1
output: 16

我不想计算反转！ 此功能与反转不同。

input: 5 2 3 4 1
dist(A): 16
inversions(A): 7

标签： algorithmsortingmergesort

Answer 1

这可以在二叉搜索树的帮助下轻松完成。您需要维护右子树中存在的节点索引的总和以及右子树中存在的节点数。因此，每当您插入一个新节点并且它向任何节点的左侧移动时，距离都会更新为

 `(no of nodes in right subtree* index of val which is to be inserted) - sum of indices of nodes present in right subtree)`

让我们来看看输入 5, 2, 3, 4, 1

第一个节点的 val 为 5，距离现在为 0；

插入后的情况2

sizeOfRightSubTree : 1 index: 1 sumOfIndicesOnRight: 0 inserted: 2, distance: 1

插入后 3

sizeOfRightSubTree : 1 index: 2 sumOfIndicesOnRight: 0 inserted: 3, distance: 3

插入后 4

sizeOfRightSubTree : 1 index: 3 sumOfIndicesOnRight: 0 inserted: 4, distance: 6

插入 1 后。请注意，它必须向左移动两次才能到达其最终位置，因此距离会更新两次。 sizeOfRightSubTree : 1 index: 4 sumOfIndicesOnRight: 0 sizeOfRightSubTree : 3 index: 4 sumOfIndicesOnRight: 6 inserted: 1, distance: 16

以下是java代码

public class DistanceFromSortedArray
{
 class Node {
    int val;
    Node left;
    Node right;
    int index;
    int sumOfIndicesOnRight;
    int sizeOfRightSubTree;


    Node(int num, int index)
    {
        this.val = num;
        this.index = index;
        sizeOfRightSubTree = 1;
        sumOfIndicesOnRight = index;
    }


    void addIndexToRight(int index)
    {
        sizeOfRightSubTree++;
        sumOfIndicesOnRight += index;
    }


    int distance(int index)
    {
        return sizeOfRightSubTree*index - sumOfIndicesOnRight;
    }
}

private Node head;
private int distance;

public int calculate(int[] nums){
    head = null;
    distance = 0;
    for(int i=0; i<nums.length; i++){
        insert(nums[i], i);
    }
    return distance;
}


private void insert(int num, int index)
{
    Node toInsert = new Node(num, index);
    if(head == null){
        head = toInsert;
        return;
    }

    Node current = head;
    Node previous = null;
    while (current != null){
        previous = current;
        if(current.val > num){
            distance += current.distance(index);
            current = current.left;
        }
        else {
            current.addIndexToRight(index);
            current = current.right;
        }
    }


    if(previous.val > num){
        previous.left = toInsert;
    }
    else {
        previous.right = toInsert;
    }

}
}

这里有几个测试用例

@Test
public void calculate()
{
    int[] nums = {5, 2, 3, 4, 1};
    assertEquals(16, new DistanceFromSortedArray().calculate(nums));
}


@Test
public void reverseCalculate()
{
    int[] nums = {5, 4, 3, 2, 1};
    assertEquals(20, new DistanceFromSortedArray().calculate(nums));
}

@Test
public void SizeTwoCalculate()
{
    int[] nums = {4, 5};
    assertEquals(0, new DistanceFromSortedArray().calculate(nums));

     int [] nums2 = {5, 4};
    assertEquals(1, new DistanceFromSortedArray().calculate(nums2));
}


@Test
public void twistedCalculate()
{
    int[] nums = {8, 3, 6, 5, 7, 1};
    assertEquals(26, new DistanceFromSortedArray().calculate(nums));
}

@Test
public void AllSameCalculate()
{
    int[] nums = {1, 1, 1, 1, 1, 1};
    assertEquals(0, new DistanceFromSortedArray().calculate(nums));
}