逆序对
本文最后更新于:2021年4月2日 上午
代码模板
1 |
|
代码原理
归并排序
逆序需要的是判断前面数字比后面大的时候组成一个逆序对
,而为了扫描的过程中只扫描一部分,不全部扫描即可得出答案,达到优化的目的,这里采用归并排序的思路,在分为A和B两组数组的同时,如果判断到了A中有一个数字比B中另外一个数字大的话,就可以很肯定的判断A之后的数字和该小的B数字都可以组成逆序对,因此可以达到简化运算量的效果。
注意
- 对于结束的情况返回
return 0
- 由于分治的过程中十分有可能出现代码规模超过
int
的情况,所以这里会使用long long
进行数据的定义。 - 由于等于的情况并不算逆序对,所以在判断
if
的时候要把等于号带上 - 通过先对最原始的”大片段“进行计算逆序对的数量,然后逐渐细化扫描更小的逆序对的数量,在扫描到return之后加起来返回的就是整个数列全部情况的逆序对的总数了。
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!