文章背景：
在复习算法及数据结构时，找到了面试笔试题目，下面我们来看看题目：
（学习视频分享：java教学视频）
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
输入描述:
题目保证输入的数组中没有的相同的数字
数据范围：
对于%50的数据,size<=10^4
对于%75的数据,size<=10^5
对于%100的数据,size<=2*10^5
分析：
这道题目很好直接求解，不过时间复杂度在o(n*n) , 最开始拿到这题没经过思考，直接dp写完了，然后发现，dp还不如直接求解，都是o(n*n)的复杂度，dp还占用了2*10^5的空间，下面是直接，求法和dp ,都超时了。
（更多相关面试题推荐：java面试题及答案）
代码分享：
//直接求法 ,超时
public class solution{
public static int sum;
public static int InversePairs(int [] array) {
dp(array);
return sum;
}
public static void dp(int []array){
for(int i = array.length - 1 ; i > 0 ; i --){
for(int j = i - 1 ; j >= 0 ; j--){
if(array[j] > array[i]){
sum += 1;
}
}
sum %= 1000000007;
}
}
}public class solution{
//一维数组dp
public static int sum;
public static int InversePairs(int [] array) {
dp(array);
return sum;
}
public static int count[] = new int[200004];
public static void dp(int []array){
for(int i = array.length - 1 ; i > 0 ; i --){
for(int j = i - 1 ; j >= 0 ; j--){
if(array[j] > array[i]){
count[j] = count[j+1]+1;
}else {
count[j] = count[j+1];
}
}
sum += count[0];
sum %= 1000000007;
for(int k = 0 ; k < array.length ; k ++)
count[k] = 0;
}
}
}dp在这里都是多余的，
下面是归并排序解决问题，不了解归并排序可以看我前一篇博客 归并排序：
public class solution{
//归并排序AC
public static int cnt ;
public static int InversePairs(int [] array) {
if(array != null){
RecusionSorted(array,0,array.length - 1);
}
return cnt%1000000007;
}
public static void MegerArray(int[] data, int start, int mid, int end) {
int temp[] = new int[end-start+1];
int i = mid;
int j = end;
int m = mid+1;
int z = 0;
while(j >= m && i >= start) {
if(data[i] > data[j]) {
temp[z++] = data[i--];
cnt += (j-mid)%1000000007;
cnt %= 1000000007;
}else {
temp[z++] = data[j--];
}
}
while(j >= m) {
temp[z++] = data[j--];
}
while(i >= start) {
temp[z++] = data[i--];
}
for(int k = start ; k <= end ; k ++) {
data[k] = temp[end - k];
}
}
public static void RecusionSorted(int data[] , int start , int end ) {
if(start < end) {
int mid = (start + end) >> 1;
RecusionSorted(data,start,mid);
RecusionSorted(data,mid+1,end);
MegerArray(data,start,mid,end);
}
}
}相关推荐：java入门教程
以上是java面试之归并排序的应用的详细内容。更多信息请关注PHP中文网其他相关文章！
