java简单实现数组中的逆序对

时间:2021-05-19

题目描述:

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

解题思路:

一开始一头雾水,后面想到了使用归并排序的思想,其实有多少个逆序对,就是归并排序的时候,后面的数要超越前面多少个,嗯,好像不是很好说,要不然直接看代码吧。还要注意,题目当中说要输出取模的结果,这说明数据可能非常大,所以如果只是单纯的在最后取模的话可能还是无法避免数据太大的影响,所以我们在每次更新count的时候就对其进行取模运算。

刚好又练习了一遍归并排序,记录一下

public class Solution { int count; public int InversePairs(int [] array) { count = 0; if(array != null){ divPairs(array, 0, array.length-1); } return count%1000000007; } public void divPairs(int[] array, int start, int end){ if(start >= end) return; int mid = (start + end)>>1; divPairs(array, start, mid); divPairs(array, mid+1, end); mergePairs(array, start, mid, end); } public void mergePairs(int[] array, int start, int mid, int end){ int i = start, j = mid+1, k = 0; int[] temp = new int[end-start+1]; while(i <= mid && j <= end){ if(array[i] <= array[j]){ temp[k++] = array[i++]; }else{ temp[k++] = array[j++]; count += mid - i + 1; count %= 1000000007; } } while(i <= mid){ temp[k++] = array[i++]; } while(j <= end){ temp[k++] = array[j++]; } for(int x = 0; x < temp.length; x++){ array[start+x] = temp[x]; } }}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。

声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。

相关文章