您的位置 首页 java

剑指offer(三十五)-数组中的逆序对(Java版)

描述

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

示例1

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

返回值:7

第一种解法,暴力解法,循环遍历,把所有情况依次统计出来,代码如下,但是很遗憾,功能没问题,由于时间过长,不能通过所有测试用例。所以提交显示不通过。

 public int firstInversePairs(int [] array) {
    int count = 0;
    if(null == array || array.length < 1){
        return 0;
    }
    for (int i = 0; i < array.length; i++) {
        int num = array[i];
        for (int j = i+1; j < array.length; j++) {
            if(num > array[j]){
                count++;
            }
        }
    }
    return count%1000000007;
}  

第二种解法,我也是看了别人的思路,才整出来的,简单来说,使用归并排序来解决问题,归并排序是基础,在排序的过程中,判断逆序对的数量即可。代码如下

  private  int count = 0;
public int secondInversePairs(int [] array) {
        if(null == array || array.length < 1){
            return count;
        }
        int[] tmp = new int[array.length];
        mergeSort(array,0,array.length-1,tmp);
        return count % 1000000007;
    }


    public void mergeSort(int[] arr, int start,int end,int[] tmp){
        if(start < end){
            int mid = (start + end)/2;
            mergeSort(arr,start,mid,tmp);
            mergeSort(arr,mid+1,end,tmp);
            merge(arr,tmp,start,end,mid);
        }
    }

    public void merge(int[] arr,int[] tmp,int left,int right,int mid){
        int i = left;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= right ){
            if(arr[i] < arr[j]){
                tmp[k++] = arr[i++];
            }else {
                tmp[k++] = arr[j++];
                count = (count + mid - i + 1) % 1000000007;
            }
        }
        while (i <= mid){
            tmp[k++] = arr[i++];
        }
        while (j <= right){
            tmp[k++] = arr[j++];
        }
        k = 0;
        for ( i = left; i <= right; i++) {
            arr[i] = tmp[k++];
        }
    }  

文章来源:智云一二三科技

文章标题:剑指offer(三十五)-数组中的逆序对(Java版)

文章地址:https://www.zhihuclub.com/182009.shtml

关于作者: 智云科技

热门文章

网站地图