剑指 Offer 51. 数组中的逆序对

本问题对应的 leetcode 原文链接:剑指 Offer 51. 数组中的逆序对
具体对应打卡问题看这里:【排序算法运用】剑指 Offer 51. 数组中的逆序对

问题描述

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

示例1 :

输入: [7,5,6,4]
输出: 5

限制:

0 <= 数组长度 <= 50000

解题思路

视频讲解直达: 本题视频讲解

代码实现

class Solution {
    public int reversePairs(int[] nums) {
        if(nums == null || nums.length <= 1){
            return 0;
        }
        return mergeSort(nums, 0, nums.length - 1);
    }

    int mergeSort(int[] nums, int left, int right){
        if(left >= right){
            return 0;
        }
        int mid = (right - left) / 2 + left;
        int x1 = mergeSort(nums, left, mid);
        int x2 = mergeSort(nums, mid + 1, right);
        int x3 = merge(nums, left, mid, mid+1, right);

        return x1 + x2 + x3;
    }

    int merge(int[] nums, int l1, int r1, int l2, int r2){
        int[] temp = new int[r2 - l1 + 1];
        int count = 0;
        int i = l1, j = l2, k = 0;
        while(i <= r1 && j <= r2){
            if(nums[i] > nums[j]){
                count = count + (l2 - i);
                temp[k++] = nums[j++];
            }else{
                temp[k++] = nums[i++];
            }
        }
        while(i <= r1) temp[k++] = nums[i++];
        while(j <= r2) temp[k++] = nums[j++];

        // 把临时数组复制回原数组
        k = 0;
        for(i = l1; i <= r2; i++){
            nums[i] = temp[k++];
        }

        return count;
    }
}

复杂度和归并排序一样
时间:O(nlogn)
空间:O(n)

发表回复

后才能评论