判断题 适中
#24878

在一个数组中,如果两个元素a [i] 和a [j]满足i < j 且a [i] > a [j],则a [i] 和a [j]是一个逆序对。 下面代码可以正确统计数…

在一个数组中,如果两个元素a [i] 和a [j]满足i < j 且a [i] > a [j],则a [i] 和a [j]是一个逆序对。

下面代码可以正确统计数组a 区间[l ,r] 内的逆序对总数。

cnt = 0
def merge_count(a , l , m , r):
    global cnt
    i = l
    j = m + 1
    while i <= m and j <= r:
        if a [i] <= a [j]: 
            i += 1
        else:
            cnt += (m - i + 1)
            j += 1
if __name__  == "__main__":
    a = [2 , 4 , 1 , 3]
    merge_count(a , 0 , 1 , 3)
    print(f "跨区间逆序对数量:{cnt}")


未登录也能判分,登录后才会记录
答案与解析
正确答案:错
解析
使用分治法将数组递归分割为子区间,通过归并排序过程中的合并阶段统计逆序对。在合并两个有序子区间时,设置双指针分别指向左右区间的起始位置,当右区间元素小于左区间当前元素时,说明左区间剩余元素均与右区间当前元素构成逆序对,累计左区间剩余元素个数至计数器。每次合并操作完成后,确保该区间内元素有序,不影响上层逆序对的正确统计。全局计数器在每次满足逆序条件时更新,最终返回区间[l, r]内的总逆序对数。算法正确性依赖于归并过程中跨区间逆序对的精确捕获与子区间内部逆序对的递归处理。