Как изменить сортировку слиянием для вычисления расстояния массива от отсортированного массива?

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

Answer 1

Вы можете решить эту проблему, вставляя числа по одному в отсортированную последовательность и поддерживая массив суффиксных сумм.Вот как это работает:

Для каждого элемента в массиве есть пара.Один содержит само число, а другой - его индекс.Теперь создайте другой массив и попробуйте вставить его в отсортированную последовательность.

Например: [(5, 1), (2, 2), (3, 3), (4, 4), (1, 5)]

Вставка 5

[(5, 1)]

Вставка 2

[(2, 2), (5, 1)] => способствует (1 * 2 - 1) => 1

Вставка 3

[(2, 2), (3, 3), (5, 1)] => способствует (1 * 3 - 1) => 2

Вставка 4

[(2, 2), (3, 3), (4, 4), (5, 1)] => способствует (1 * 4 - 1) => 3

Вставить 1

[(1, 5), (2, 2), (3, 3), (4, 4), (5, 1)] => способствует (5 * 4- (10)) => 10

Суммируйте все вклады, и вы получите 16

Сложность времени: O (N * log N)

Answer 2

Это легко сделать с помощью бинарного дерева поиска.Вам необходимо сохранить сумму индексов узлов, присутствующих в правом поддереве, и количества узлов, присутствующих в правом поддереве.Таким образом, всякий раз, когда вы вставляете новый узел, и он идет влево от любого узла, расстояние будет обновляться на

 `(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));
}

Answer 3

Если вы знаете, как вычислить число инверсии массива с помощью сортировки слиянием, вы решите это, изменив несколько строк кода.

обратите внимание на детали.

// struct to store the values
//
struct pa {
    int value, index;
};

// The merge step
// A is the left part, while B is the right part
// a_cnt is the number of elements in A
void merge(pa A[], pa B[], int a_cnt, int b_cnt) {
    int st = 0;
    int tmp_sum = 0;
    for (int i = 0; i < a_cnt; ++i) {
        while (st < b_cnt && B[st].value < A[i].value) {
            tmp_sum += B[st].index;
            st++;
        }
        ans += (tmp_sum - st * A[i].index)
    }

    // origional merge code here
}