文章背景：
在复习算法及数据结构时，找到了面试笔试题目，下面我们来看看题目：
（学习视频分享：java教学视频）
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
立即学习“Java免费学习笔记（深入）”；
输入描述:
题目保证输入的数组中没有的相同的数字
数据范围：
对于%50的数据,size<=10^4
对于%75的数据,size<=10^5
白瓜面试
白瓜面试 – AI面试助手,辅助笔试面试神器
40 查看详情
对于%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 > 1;RecusionSorted(data,start,mid);RecusionSorted(data,mid+1,end); MegerArray(data,start,mid,end);} }}
相关推荐：java入门教程
以上就是java面试之归并排序的应用的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/569783.html
微信扫一扫 
支付宝扫一扫 
