我要招人

去企业版

首页 > 试题广场 >

数组中的逆序对

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

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

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。即输出P mod 1000000007

数据范围：对于 $50\%$ 的数据, $size\leq 10^4$
对于 $100\%$ 的数据, $size\leq 10^5$

数组中所有数字的值满足 $0 \le val \le 10^9$

要求：空间复杂度 $O(n)$ ，时间复杂度 $O(nlogn)$

输入描述:

题目保证输入的数组中没有的相同的数字

示例1

输入

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

输出

示例2

输入

[1,2,3]

输出

算法知识视频讲解

牛客题解官

发表于 2020-06-02 11:16:05

精华题解描述这是一篇针对初学者的题解。讲述了如何从归并排序的思想到解决本题。知识点：递归难度：二星题解题目描述：给定一个数组arr，数组元素各不相同，求arr[i] > arr[j] 且 i < j的个数。首先还是提出两个问题，带着问题来看题解，我觉得效率更好。Q1：为什么归并排序需展开全文

LaN666

发表于 2021-06-23 23:12:10

精华题解 35、数组中的逆序对解题思路：题目简单易懂就不做过多解释，一开始很容易想到解题可以使用暴力法去统计所有的逆序对，但是这样的话时间复杂度是O(n2) 方法一：暴力统计法先直接给出暴力法的代码： public class Solution { public int InversePai 展开全文

牛客题解官

发表于 2022-04-22 11:41:36

精华题解题目的主要信息：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求一个数组的全部逆序对，答案对1000000007取模保证输入的数组中没有的相同的数字举一反三：学习完本题的思路你可以解决如下题目： BM.12 单链表的排序 BM.5 合并k 展开全文

GhostLX

发表于 2021-06-24 16:08:59

精华题解题目陈述大意：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。即输出P%1000000007 算法一：朴素做法算法思路最显然的思路就是枚举，枚举第i个数，下标比他大的所展开全文

江南好___

发表于 2021-06-23 15:32:30

精华题解描述题目描述把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。示例输入：7 返回值：8引言对于这种看似复杂的题目，不妨先通过简单的例子计算，进而推到出完整过程展开全文

一叶浮尘

发表于 2019-08-21 08:33:04

题目描述在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。即输出P%1000000007输入描述:题目保证输入的数组中没有的相同的数字数据范围：对于%50的数据,size& 展开全文

Ironxin

发表于 2020-04-13 22:02:46

题目描述在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。即输出P%1000000007 首先知道什么是逆序对，{3,1,2}的逆序对就是{3,1}和{3,2}。然后，取模展开全文

卡2

发表于 2021-12-07 21:35:22

归并排序得结果问题转化：求逆序对就是统计有多少个前大后小的数对，问题和归并两个有序数组求前大后小数对一样。所以现在的问题变为统计子问题中逆序对的个数。递归模型变形：递归按照标准的归并排序来，注意的是统计个数，当出现nums[i]>nums[j]时，统计所有前半段区间内比nums[j]大的数展开全文

tonyjxc

发表于 2022-01-17 20:23:15

排序第二题 jz51 难题！！因为取余数 c++计算不了所以用python 结合了递归、快排、归并、分治四个算法大致就是取一个数（快排）记录下所有比它小的，比它大的，（归并，分治）再把这两部分递归调用 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规展开全文

牛客756272137号

发表于 2022-02-20 19:21:50

归并排序，在合并的时候加一句 countinverse += len(left)-l 计算逆序对的个数，最后返回左逆序对+本次逆序对+右逆序对的数量【图源网络侵删】 # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param data int整型一展开全文

中工升达预备毕业生

发表于 2019-11-25 20:36:22

入门思路：冒泡排序的交换次数，即数组逆序对数 -> 时间复杂度O(n^2) -> 归并排序求解O(logn)// 这个题目有很多经典的解法：冒泡排序、归并排序、树状数组、线段树等等，可惜现在老了，写不了啦。 public class Solution { static int 展开全文

FreeLoop6

发表于 2020-03-13 14:41:10

归并排序递归版：（便于理解此题）先分后合，分：sort（start，end），合：merge（start，mid，end）代码：public class Solution { private int count; public int InversePairs(int [] array) 展开全文

常喝水

发表于 2019-12-25 15:28:21

利用归并排序的思想：在数组分裂的过程中，把left和right从第i个位置开始进行比较，哪个小就把它加入merged中，由于此时left和right是分别有序的，如果left[i]>right[j]，证明left[i:]都大于right[j]，此时的逆序对要加len(left)-i 例如展开全文

请给我半节香烟

发表于 2022-03-04 16:12:32

归并排序处理，最后返回的值就是交换的次数。 int num = 0; public int InversePairs(int [] array) { int []temp = new int[array.length];//在排序前，先建好一个长度等于原数组长度的展开全文

NumPy

发表于 2021-08-12 13:11:45

一、题目描述题目大意：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。即输出P%1000000007注意审题：前面一个数字要严格大于后面的数字，且要对结果取模二、算法1（暴展开全文

问题信息

数组

难度：

1030条回答 6186收藏 171572浏览

通过挑战的用户

查看代码

葳蕤自重光

2023-03-11 20:20:12
空的态度

2022-12-06 16:25:33
牛客89418...

2022-10-27 15:55:36
牛客74843...

2022-10-16 14:27:16
牛客10112...

2022-09-18 20:27:28

数组中的逆序对

输入描述:

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题