逆序对数-剑指offer-Java

我会带着你远行 2021-12-03 22:47 234阅读 0赞

### 题目描述： ###

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。

输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

### 解题思路： ###

1、前面的数字大于后面的数字，是指前面所有的数字与后面某个数字比较，是所有，不是当前的前面

2、从小到大冒泡排序，冒泡的次数就是前面大于后面的对数,可是复杂度较高。

3、归并排序，

> 1.  package pratice718;
> 2.  import java.util.Stack;
> 3.  public class ReverseOrder \{
> 4.  //题目描述：
> 5.  //在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
> 6.  //输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
> 7.  //解题思路：
> 8.  //1、前面的数字大于后面的数字，是指前面所有的数字与后面某个数字比较，是所有，不是当前的前面
> 9.  //2、从小到大冒泡排序，冒泡的次数就是前面大于后面的对数,可是复杂度较高。
> 10. //3、归并排序，
> 11.     static int count=0;
> 12.     public static int InversePairs(int \[\] array) \{
> 13.        if(array==null || array.length==0) return 0;
> 14.        mSort(array,0,array.length-1);
> 15.        return count;
> 16.     \}
> 17.     public static void mSort(int array\[\],int start,int end)\{
> 18.         if(start>=end) return;
> 19.         int middle = start+(end-start)/2;
> 20.         mSort(array,start,middle);
> 21.         mSort(array,middle+1,end);
> 22.         
> 23.         merge(array,start,end,middle);
> 24.     \}
> 25.     public static void merge(int array\[\],int start,int end,int middle)
> 26.     \{
> 27.         int temp\[\] = new int\[end-start+1\];
> 28.         int i=start,j=middle+1,k=0;
> 29.         while(i<=middle && j<=end)\{
> 30.             if(array\[i\]<array\[j\])
> 31.                 temp\[k++\] = array\[i++\];
> 32.             else\{
> 33.                 temp\[k++\] = array\[j++\];
> 34.                 count += middle - i+1;
> 35.                 count%=1000000007;
> 36.             \}
> 37.         \}
> 38.         while(i<=middle)
> 39.             temp\[k++\] = array\[i++\];
> 40.         while(j<=end)
> 41.             temp\[k++\] = array\[j++\];
> 42.         for(k=0;k<temp.length;k++)
> 43.         \{
> 44.             array\[start+k\] = temp\[k\];
> 45.         \}
> 46.     \}
> 47.     public static void main(String\[\] args) \{
> 48.         int array\[\] = \{1,2,3,4,5,6,7,0\};
> 49.         System.out.println("result: "+InversePairs(array));        
> 50.     \}
> 51. \}

**扫码关注一起随时随地学习！！！就在洋葱攻城狮，更多精彩，等你来！！**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70]: /images/20211203/3d9464fa97bb4b608723d358c7458458.png