Блог

Я пытаюсь выполнить задание Алгоритмического курса, предлагаемого Калифорнийским университетом Сан-Диего на Coursera, и у меня возникла проблема…

Я использовал алгоритм сортировки слиянием для подсчета инверсий путем суммирования количества элементов слева в левой массива ( a массив) для подсчета каждый раз, когда вы сливаете элемент из массива в правильном ( b массив), но я действительно не знаю, почему он не выдает правильное количество инверсий иногда, и это сводит меня с ума, вот код, и некоторые тестовые случаи:

 import sys

def get_number_of_inversions(a, left, right):
    number_of_inversions = 0
    # print(a)
    if right - left <= 1:
        return number_of_inversions
    mid = (left   right) // 2
    number_of_inversions = get_number_of_inversions(a, left, mid)
    number_of_inversions = get_number_of_inversions(a, mid, right)

    left_side = a[left:mid]
    right_side = a[mid:right]

    while len(left_side) > 0 and len(right_side) > 0:
        if left_side[0] <= right_side[0]:
            a[left] = left_side[0]
            left  = 1
            left_side.remove(left_side[0])
        else:
            a[left] = right_side[0]
            left  = 1
            right_side.remove(right_side[0])
            number_of_inversions  = len(left_side)
    if len(left_side) == 0:
        a[left] = right_side[0]
        left  = 1
    else:
        a[left] = left_side[0]
        left  = 1
    return number_of_inversions


if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    print(int(get_number_of_inversions(a, 0, len(a))))
 

Тестовые примеры:

 6
9 8 7 3 2 1 
 

Этот должен давать 15, но он дает 12

 6
3 1 9 3 2 1
 

Этот должен давать 9, но он дает 8