BM20 数组中的逆序对

1.题目描述

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


数据范围:  对于 50%50% 的数据, 𝑠𝑖𝑧𝑒≤104size≤104
对于 100%100% 的数据, 𝑠𝑖𝑧𝑒≤105size≤105

数组中所有数字的值满足 0≤𝑣𝑎𝑙≤1090≤val≤109
 

要求:空间复杂度 𝑂(𝑛)O(n),时间复杂度 𝑂(𝑛𝑙𝑜𝑔𝑛)O(nlogn)

输入描述:

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

示例1

输入:

[1,2,3,4,5,6,7,0]

返回值:

7

示例2

输入:

[1,2,3]

返回值:

0

2.解题思路

  1. 常规思路就是使用O(n^2)的时间复杂度暴力遍历这个数组,枚举每一对组合,统计所有的逆序对个数,需要对这个思路进行优化。
  2. 基于分治的思想,可以使用归并排序来解决这一题。归并排序时,每一次都会基于中心点mid,将数组拆分成leftNums和rightNums两个部分,直到leftNums和rightNums为长度等于1的子数组时,就能保证子数组是有序的,然后就需要对这两个有序的子数组进行融合,在融合时,我们可以发现如果当前rightNums[j] < leftNums[i],那么leftNums i下标及往后的所有元素都会和rightNums[j]形成一个逆序对,所以直接统计count += leftNums.length - i;这样就避免了内层的for循环

3.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    private int count = 0;

    public int InversePairs (int[] nums) {
        // write code here
        sort(nums);
        return count;
    }

    //归并排序
    public int[] sort(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums;
        int mid = n / 2;
        int[] leftNums = sort(Arrays.copyOfRange(nums,0,mid));
        int[] rightNums = sort(Arrays.copyOfRange(nums,mid,n));
        return merge(leftNums,rightNums);
    }

    public int[] merge(int[] leftNums,int[] rightNums) {
        int m = leftNums.length, n = rightNums.length;
        int[] result = new int[m+n];
        int i = 0, j = 0, p = 0;
        while (i < m && j < n) {
            if (leftNums[i] < rightNums[j]) {
                result[p++] = leftNums[i++];
            } else {
                //统计逆序对
                count += (m - i);
                count %= 1000000007;
                result[p++] = rightNums[j++];
            }
        }
        while (i < m) {
            result[p++] = leftNums[i++];
        }
        while (j < n) {
            result[p++] = rightNums[j++];
        }
        return result;
    }
}

相关推荐

  1. BM20 数组

    2024-07-20 14:34:04       26 阅读
  2. Acwing---788.数量

    2024-07-20 14:34:04       51 阅读
  3. 剑指offer面试题36 数组

    2024-07-20 14:34:04       43 阅读
  4. 数组存放

    2024-07-20 14:34:04       56 阅读
  5. 2024-07-20 14:34:04       49 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-20 14:34:04       94 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-20 14:34:04       102 阅读
  3. 在Django里面运行非项目文件

    2024-07-20 14:34:04       83 阅读
  4. Python语言-面向对象

    2024-07-20 14:34:04       92 阅读

热门阅读

  1. SpringBoot使用Jasypt加密

    2024-07-20 14:34:04       23 阅读
  2. Linux 之 awk命令详解

    2024-07-20 14:34:04       24 阅读
  3. 电机线电流与转差率曲线理论推导

    2024-07-20 14:34:04       21 阅读
  4. 【HTTP 与 HTTPS 介绍与区别】

    2024-07-20 14:34:04       22 阅读
  5. (81)组合环路--->(05)避免组合环路

    2024-07-20 14:34:04       25 阅读
  6. 3.Implementing Controllers

    2024-07-20 14:34:04       20 阅读
  7. axios(ajax请求库)

    2024-07-20 14:34:04       23 阅读
  8. C++题目_中缀表达式转后缀表达式(常考)

    2024-07-20 14:34:04       24 阅读
  9. 差分进化(Differential Evolution)算法

    2024-07-20 14:34:04       28 阅读
  10. Cyclic Operations

    2024-07-20 14:34:04       24 阅读
  11. VScode如何进行调试

    2024-07-20 14:34:04       22 阅读