逆序对(deseq) 【问题】给定一个序列a1,a2,…,an,如果存在i < j并且ai > aj,那么我们称之为逆序对,求逆序对的数目 输入:第一行为n,表示序列长度,接下来的n行,第i+1行表示序列中的第i个数。 输出:所有逆序对总数 样例输入: 4 3 2 3 2 样例输出: 3
时间: 2023-12-06 21:41:27 浏览: 118
分治法求数组中的逆序数
这道题可以使用归并排序的思想来解决,每次在归并的时候统计逆序对的数量。
具体来说,我们将原序列分成左右两个子序列,先递归求解左子序列中的逆序对数量和右子序列中的逆序对数量,然后再统计左右两个子序列合并后的逆序对数量。
统计合并后的逆序对数量时,我们可以使用一个辅助数组来存储合并后的序列,然后从左右两个子序列的末尾开始比较,如果左子序列的当前元素大于右子序列的当前元素,则说明左子序列中当前元素及其后面的所有元素都能与右子序列当前元素构成逆序对,因为左子序列中当前元素及其后面的元素都大于右子序列当前元素。
具体实现可以参考下面的代码:
阅读全文