欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指offer——数组中的逆序对

程序员文章站 2022-05-10 15:33:36
...

剑指offer——数组中的逆序对

题目描述

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

输入描述:
题目保证输入的数组中没有的相同的数字

数据范围:

对于%50的数据,size<=10^4

对于%75的数据,size<=10^5

对于%100的数据,size<=2*10^5
示例1

输入:1,2,3,4,5,6,7,0

输出:7

第一解答思路:暴力求解

利用两个for循环,遍历求解,时间复杂度为O(n*n)。

package com.offer;

class Solution {
    public static int InversePairs(int [] array) {
        int len=array.length;
        if(len==0 || array==null){
            return 0;
        }
        int p=0;
        for(int i=0;i<len;i++){
            for(int j=i+1;j<len;j++){
                if(array[i]>array[j]){
                    p++;
                }
            }
        }
        return p%1000000007;
    }
}
public class InversePairsTest {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] a={1,2,3,4,5,6,7,0};
        System.out.println(Solution.InversePairs(a));
    }

}

第二解答思路:利用归并排序,显著提高查找效率

public class Solution {
    int count=0;
    public int InversePairs(int [] array) {
        if(array.length==0 || array==null){
            return 0;
        }
        mergeSort(array,0,array.length-1);
        return count;
    }
    //归并排序(从上往下)
    public void mergeSort(int[] a,int low,int high){
        //一定要写递归出口,不然会报错:Exception in thread "main" java.lang.*Error
        if(low>=high){
            return;
        }
        int mid=(high+low)>>1;
        mergeSort(a,low,mid);
        mergeSort(a,mid+1,high);
        merge(a,low,mid,high);
    }
    //将一个数组中的两个相邻有序区间合并成一个
    public void merge(int[] a,int low,int mid,int high){
        int[] temp=new int[high-low+1];
        int i=low,j=mid+1,k=0;//i代表左半部分,j代表右半部分,k为临时数组的下标
        while(i<=mid && j<=high){
            if(a[i]<=a[j]){
                temp[k++]=a[i++];
            }else{
                temp[k++]=a[j++];
                count += mid-i+1;
                //核心算法。因为前半部分为有序序列,则如果a[i]>a[j],则a[i]到a[mid]之间的元素都大于a[j]
                //因为j++,所以要一次求完,即mid-i+1
                count %=1000000007;
            }
        }
        while(i<=mid){
            temp[k++]=a[i++];
        }
        while(j<=high){
            temp[k++]=a[j++];
        }
        for(int m=0;m<temp.length;m++){
            a[low+m]=temp[m];
        }
    }
}

参考学习资料:JAVA算法——排序之归并排序