题目描述
题解
暴力方法(超时)
就是使用一个双循环结构计算出全部的逆序对, 结果超时:
1 | class Solution { |
归并排序
如果编写递归函数,每一次都一分为二拆分数组的子区间,然后在方法栈弹出的时候,一步一步合并两个有序数组,最后完成排序工作。
而计算逆序数就发生在排序的过程中,利用了「排序」以后数组的有序性。
- 关键在于合并两个有序数组的步骤, 利用数组的部分有序性, 一下子计算出一个数之前或者之后元素的逆序的个数
- <分>的时候什么也不做, <合>的时候计算逆序对的个数
- 排序工作是必要的, 正是因为排序才能在下一轮利用顺序关系加快逆序数的计算,也能避免重复计算
1 | public class jz51 { |