#yyds干货盘点# 面试必刷TOP101：数组中的逆序对

#yyds干货盘点# 面试必刷TOP101：数组中的逆序对

1.简述：

描述

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

输入描述：

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

示例1

输入：

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

返回值：

7

示例2

输入：

[1,2,3]

返回值：

0

2.代码实现：

public class Solution { int count = 0; public int InversePairs(int [] array) { // 长度小于2则无逆序对 if(array.length < 2) return 0; // 进入归并 mergeSort(array,0,array.length-1); return count; } public void mergeSort(int[] array,int left,int right){ // 找分割点 int mid = left+(right-left)/2; if(left < right){ // 左子数组 mergeSort(array,left,mid); // 右子数组 mergeSort(array,mid+1,right); // 并 merge(array,left,mid,right); } } public void merge(int[] array,int left,int mid,int right){ // 创建临时数组，长度为此时两个子数组加起来的长度 int[] arr = new int[right-left+1]; // 临时数组的下标起点 int c = 0; // 保存在原数组的起点下标值 int s = left; // 左子数组的起始指针 int l = left; // 右子数组的起始指针 int r = mid+1; while(l <= mid && r <= right ){ // 当左子数组的当前元素小的时候，跳过，无逆序对 if(array[l] <= array[r]){ // 放入临时数组 arr[c] = array[l]; // 临时数组下标+1 c++; // 左子数组指针右移 l++; }else{ // 否则，此时存在逆序对 // 放入临时数组 arr[c] = array[r]; // 逆序对的个数为 左子数组的终点- 当前左子数组的当前指针 count += mid+1-l; count %= 1000000007; // 临时数组+1 c++; // 右子数组的指针右移 r++; } } // 左子数组还有元素时，全部放入临时数组 while(l <= mid) arr[c++] = array[l++]; // 右子数组还有元素时，全部放入临时数组 while(r <= right) arr[c++] = array[r++]; // 将临时数组中的元素放入到原数组的指定位置 for(int num:arr){ array[s++] = num; } }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。