用的是mergesort的思路，对于一个数组，我们将其分为前后两列，我们可以先分别统计前后各自的逆序对，然后再统计两者之间的逆序对。统计两者之间的逆序对这个在merge的过程中就可以做，而且很简单，对于merge过程中的i,j，i和j分别是前后两个的指针，如果nums[i]<nums[j]，前i个和前j个的逆序对是0，如果nums[i]>=nums[j]，那么前i个和前j个的逆序对是
比如对于左：[1，2，3，4]右：[2，5]。 其中 i指向3，j指向2。 那么 逆序数就是 mid - i + 1 也就是 3 - 2 + 1 = 2 即（3，2)和 (4，2)。 其原因在于如果 3 大于 2，那么 3 后面不用看了，肯定都大于 2。
https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/jian-dan-yi-dong-gui-bing-pai-xu-python-by-azl3979/
面试题51. 数组中的逆序对 题目来源：https://leetcode-cn.com/problems/shu-...
面试题51. 数组中的逆序对 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入...
面试题51. 数组中的逆序对 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入...
面试题51. 数组中的逆序对 用的是mergesort的思路，对于一个数组，我们将其分为前后两列，我们可以先分别统...
剑指 Offer 51. 数组中的逆序对[https://leetcode-cn.com/problems/shu...
题目 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中...
1.题目链接 剑指 Offer 51. 数组中的逆序对[https://leetcode-cn.com/probl...
题目链接： 剑指offer 50-59 目录： 50. 第一个只出现一次的字符位置51. 数组中的逆序对52. 两...
题目描述在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组...
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序...
本文标题：面试题51. 数组中的逆序对
本文链接：https://www.haomeiwen.com/subject/hvtpxktx.html
网友评论