下面的内容主要给大家分享的是数组中的逆序对的java实现以及思路，具体包含了3组实例，感兴趣的小伙伴可以来了解一下哦。
题目：
数组中的2个数字，假如，前面一个数字比后面的数字大，那么，这2个数字就组成一个逆序对。
输入1个数字，求出该数组当中的逆序对的总数P。
并且将P对1000000007取模的结果输出。 即输出P%1000000007。
输入：
例：
输入：1,2,3,4,5,6,7,0
输出：7
思路1：
(1)暴力求解法，时间复杂度为o(n^2),空间复杂度o(1)
(2)使用归并排序的思想进行处理，时间复杂度o(nlog(n)),空间复杂度0(n)*/
代码实现：
class Solution
{
public:
int InversePairs(vector < int > data)
{
if (data.size() <= 1) return 0; //如果少于等于1个元素，直接返回0
int * copy = new int[data.size()];
//初始化该数组，该数组作为存放临时排序的结果，最后要将排序的结果复制到原数组中
for (unsigned int i = 0; i < data.size(); i++)
copy[i] = 0;
//调用递归函数求解结果
int count = InversePairCore(data, copy, 0, data.size() - 1);
delete[] copy; //删除临时数组
return count;
}
//程序的主体函数
int InversePairCore(vector < int > & data, int * & copy, int start, int end)
{
if (start == end)
{
copy[start] = data[start];
return 0;
}
//将数组拆分成两部分
int length = (end - start) / 2; //这里使用的下标法，下面要用来计算逆序个数；也可以直接使用mid=（start+end）/2
//分别计算左边部分和右边部分
int left = InversePairCore(data, copy, start, start + length) % 1000000007;
int right = InversePairCore(data, copy, start + length + 1, end) % 1000000007;
//进行逆序计算
int i = start + length; //前一个数组的最后一个下标
int j = end; //后一个数组的下标
int index = end; //辅助数组下标，从最后一个算起
int count = 0;
while (i >= start && j >= start + length + 1)
{
if (data[i] > data[j])
{
copy[index--] = data[i--];
//统计长度
count += j - start - length;
if (count >= 1000000007) //数值过大求余
count %= 1000000007;
}
else
{
copy[index--] = data[j--];
}
}
for (; i >= start; --i)
{
copy[index--] = data[i];
}
for (; j >= start + length + 1; --j)
{
copy[index--] = data[j];
}
//排序
for (int i = start; i <= end; i++)
{
data[i] = copy[i];
}
//返回最终的结果
return (count + left + right) % 1000000007;
}
};思路2
代码实现：
public class Solution
{
int cnt;
public int InversePairs(int[] array)
{
cnt = 0;
if (array != null)
mergeSortUp2Down(array, 0, array.length - 1);
return cnt;
}
/*
* 归并排序(从上往下)
*/
public void mergeSortUp2Down(int[] a, int start, int end)
{
if (start >= end)
return;
int mid = (start + end) >> 1;
mergeSortUp2Down(a, start, mid);
mergeSortUp2Down(a, mid + 1, end);
merge(a, start, mid, end);
}
/*
* 将一个数组中的两个相邻有序区间合并成一个
*/
public void merge(int[] a, int start, int mid, int end)
{
int[] tmp = new int[end - start + 1];
int i = start, j = mid + 1, k = 0;
while (i <= mid && j <= end)
{
if (a[i] <= a[j])
tmp[k++] = a[i++];
else
{
tmp[k++] = a[j++];
cnt += mid - i + 1; // core code, calculate InversePairs............
}
}
while (i <= mid)
tmp[k++] = a[i++];
while (j <= end)
tmp[k++] = a[j++];
for (k = 0; k < tmp.length; k++)
a[start + k] = tmp[k];
}
}思路3：
这道题，是归并排序的典型应用。
归并排序的基本思想是分治，在治的过程中有前后数字的大小对比，这个时候就是统计逆序对的最佳时机。
代码实现：
public class Solution
{
//统计逆序对的个数
int cnt;
public int InversePairs(int[] array)
{
if (array.length != 0)
{
divide(array, 0, array.length - 1);
}
return cnt;
}
//归并排序的分治---分
private void divide(int[] arr, int start, int end)
{
//递归的终止条件
if (start >= end)
return;
//计算中间值，注意溢出
int mid = start + (end - start) / 2;
//递归分
divide(arr, start, mid);
divide(arr, mid + 1, end);
//治
merge(arr, start, mid, end);
}
private void merge(int[] arr, int start, int mid, int end)
{
int[] temp = new int[end - start + 1];
//存一下变量
int i = start, j = mid + 1, k = 0;
//下面就开始两两进行比较，若前面的数大于后面的数，就构成逆序对
while (i <= mid && j <= end)
{
//若前面小于后面，直接存进去，并且移动前面数所在的数组的指针即可
if (arr[i] <= arr[j])
{
temp[k++] = arr[i++];
}
else
{
temp[k++] = arr[j++];
//a[i]>a[j]了，那么这一次，从a[i]开始到a[mid]必定都是大于这个a[j]的，因为此时分治的两边已经是各自有序了
cnt = (cnt + mid - i + 1) % 1000000007;
}
}
//各自还有剩余的没比完，直接赋值即可
while (i <= mid)
temp[k++] = arr[i++];
while (j <= end)
temp[k++] = arr[j++];
//覆盖原数组
for (k = 0; k < temp.length; k++)
arr[start + k] = temp[k];
}
}希望以上的三种实现方式可以对你有所帮助，请继续关注本站，有更多的Java实例，可以分享给大家。