栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

AcWing 65. 数组中的逆序对-java

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

AcWing 65. 数组中的逆序对-java

AcWing 65. 数组中的逆序对 -归并排序 原题链接

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

输入一个数组,求出这个数组中的逆序对的总数。

数据范围
给定数组的长度 [0,100]。

代码案例:输入:[1,2,3,4,5,6,0]
输出:6

题解
class Solution {
    public int inversePairs(int[] a) {
//         本题是归并排序的变型
// 逆序对可以分成三种情况:1、一个是都在左边 此时逆序对数量为
// 2、一个是都在右边,此时逆序对数量
// 3、一个在左边,一个在右边,在左边的数只要大于他就构成逆序对,我们只能要统计出这些数,
// 1、2的情况 归并排序都是排好的
// if (arr[i] <= arr[j])
// tmp[k++] = arr[i++];
// else
// tmp[k++] = arr[j++];
// else中的语句即代表左边数列中的数大于右边中的数了,我们可以在此时将
// mid-i+1加到总答案中去。那么3的问题就解决了。
 
      return   merge_sort(a,0,a.length-1);
    }
      int merge_sort(int[] a , int l , int r){
        if(l >= r ) return 0 ;
        int mid = l + r >> 1;
       int res = merge_sort(a , l , mid)+ merge_sort(a, mid +1 ,r);
        int k = 0 , i = l , j =mid+1 ; 
        int [] temp = new int [r-l+1];
        while(i <= mid && j <= r){
            if(a[i] <= a [j]) temp[k++] = a[i++];
            else {
                res += mid - i +1 ;//每次都累加
                temp[k++] = a[j++] ; 
            }
        }
        while( i <= mid) temp[k++] = a [i++];
        while(j <= r ) temp[k++] = a[j++];
        for(i = l , j = 0 ; i <= r ; i++,j++){
            a[i]=temp[j];
        }
        return res;
    }
}
 

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/975908.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号