Leetcode:493. Reverse Pairs

Description:

Given an array nums, we call (i, j) an important reverse pair if i < j and nums[i] > 2*nums[j].You need to return the number of important reverse pairs in the given array.
Example1:

Input: [1,3,2,3,1]
Output: 2

Example2:

Input: [2,4,3,5,1]
Output: 3

Note:
The length of the given array will not exceed 50,000.All the numbers in the input array are in the range of 32-bit integer.

解题思路：

题目大意是说给定数组nums，定义所有满足i < j 并且nums[i] > 2 * nums[j]的数对(i, j)为“重要的逆序对”（important reverse pair），返回其个数。
一般来说最容易想到的算法就是双重遍历再加一个判断语句即可完成

int reversePairs(vector<int>& nums)
{
    int n = nums.size();
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[i] * 2)
                count++;
        }
    }
    return count;
}

但是

该算法的时间复杂度为O($n^2$),出现time limit错误，不能满足要求
因此可以采用归并算法：

1. 把数组分隔成子数组
2. 先统计出子数组内部的逆序对数目
3. 再统计两个相邻子数组之间的逆序对数目
4. 在统计逆序的过程中，同时对数组进行归并排序。

事实上就是分治法，把大问题划分为小问题加以解决。

代码

    int count;
    void checkCount(vector<int>& nums, int start, int mid, int end){
        int s = start, m = mid+1;
        while(s <= mid && m <= end) {
            if ((long)nums[s] > (long)2*nums[m]) {
                count += (mid-s+1);
                m++; 
            } else {
                s++;
            } 
        }
        sort(nums.begin()+start,nums.begin()+end+1);

        return;
    }
    void mergesort(vector<int>& nums, int start, int end) {
        if (start == end) return;
        int mid = (start+end)/2;
        mergesort(nums,start,mid);
        mergesort(nums,mid+1,end);

        checkCount(nums, start, mid,  end);

        return;
    }
    int reversePairs(vector<int>& nums) {
        if(nums.size() == 0) return 0;
        count = 0;
        mergesort(nums,0,nums.size()-1);
        return count; 
    } 

最后

以上就是可爱热狗为你收集整理的Leetcode:493. Reverse Pairs的全部内容，希望文章能够帮你解决Leetcode:493. Reverse Pairs所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。