JZ51 数组中的逆序对

题目

在数组中的两个数字    
    
    
，如果前面一个数字大于后面的数字 


     


     


，则这两个数字组成一个逆序对    
    
    
。输入一个数组,求出这个数组中的逆序对的总数P 


     


     


。并将P对1000000007取模的结果输出

 




 




 。 即输出P mod 1000000007

方法1：暴力

思路

算法实现

两个for循环

 




 




 ，如果前面的数大于后面的计数加1即可

问题

当输入数过大时   

   

   
，需要的时间会很长  

     

     

，所以此方法不行

代码

package mid.JZ51数组中的逆序对; import java.util.ArrayList; public class Solution { public int InversePairs1(int[] array) { int k = 1000000007; if (array.length <= 1) return 0; int res = 0; for (int i = 1; i < array.length; i++) { for (int j = i - 1; j >= 0; j--) { if (array[i] < array[j]) res++; } } return res % k; } }

方法2 归并排序思想

思路

先分：分呢


  




  




 ，就是将数组分为两个子数组  


  


  
，两个子数组分为四个子数组   
     
     
，依次向下分



   




   




 ，直到数组不能再分为止！ 后并：并呢 



 



 
，就是从最小的数组按照顺序合并              ，从小到大或从大到小




    




    




 ，依次向上合并










，最后得到合并完的顺序数组！ 归并统计法               ，关键点在于合并环节



     



     



 ，在合并数组的时候










，当发现右边的小于左边的时候    
    
    
，此时可以直接求出当前产生的逆序对的个数   

   

   
。

代码

package mid.JZ51数组中的逆序对; import java.util.Arrays; public class Solution { /** * 分治 * * @param array * @return */ public int count = 0; public int InversePairs(int[] array) { divMerge(array, 0, array.length-1); return count; } public void divMerge(int[] array, int left, int right) { if (left >= right) return; int mid = left + (right - left) / 2; //分左边 divMerge(array, left, mid); //分右边 divMerge(array, mid + 1, right); //合并 int i = left; int j = mid + 1; //临时数组 int[] tmp = new int[right - left + 1]; int k = 0; while (i <= mid && j <= right) { if (array[i] > array[j]) { tmp[k++] = array[j++]; count += mid - i + 1; count %= 1000000007; } else { tmp[k++] = array[i++]; } } while (i <= mid) { // 如果右边的走完了 就把左边的放到tmp后面 tmp[k++] = array[i++]; } while (j <= right) { // 如果左边的走完了 就把右边的放到tmp后面 tmp[k++] = array[j++]; } // 把排好序的tmp 移到 array中 for(int l=0; l<k; l++) { array[left++] = tmp[l]; } } public static void main(String[] args) { System.out.println(new Solution().InversePairs(new int[]{1, 2, 3, 4, 5, 6, 7, 0})); } /** * 暴力 * * @param array * @return */ public int InversePairs1(int[] array) { int k = 1000000007; if (array.length <= 1) return 0; int res = 0; for (int i = 1; i < array.length; i++) { for (int j = i - 1; j >= 0; j--) { if (array[i] < array[j]) res++; } } return res % k; } }