数组中的逆序对

[编程题]数组中的逆序对

热度指数：8068 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个int数组A和它的大小n，对于这组数能组成的任意两个数组，若前面一个大于后面一个数字，则这两个数字组成一个逆序对。请设计一种高效的算法返回A中存在的逆序对个数。要求n不大于5000。

测试样例：

[1,2,3,4,5,6,7,0],8

返回：7

算法知识视频讲解

一个小小小小萌新

发表于 2021-07-30 20:58:34

刚看题目的时候，看到这句话“对于这组数能组成的任意两个数组”，还以为要比较复杂，但后面才发现这句话应该是写错了，“两个数组”应该是“两个数字”，所以就很简单了，只要用两个for循环前后比较统计就好了 import java.util.*; public class AntiOrder { 展开全文

wayToMaster

发表于 2022-01-13 20:08:47

# -*- coding:utf-8 -*- class AntiOrder: def count(self, A, n): &nb 展开全文

胖胖不吹牛

发表于 2020-04-13 17:19:18

感觉dp可以解决很多问题啊。思路是：遍历数组。轮询时比较当前数和之前数组的最大值。大于则替换，dp[i] = dp[i-1]。小于则从前向后遍历之前数组，找到自己的位置，得到index插入。dp[i] = dp[i-1] + size-index;(这里的size是未插入之前的size 所以不需要展开全文