【分治算法】Leetcode编程题解：493. Reverse Pairs Add to List

45 阅读 0 评论 30 点赞

我是靠谱客的博主懦弱火龙果，最近开发中收集的这篇文章主要介绍【分治算法】Leetcode编程题解：493. Reverse Pairs Add to List，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目：

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.

样例：

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

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

要求：

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.

题目刚开始采用二分查找解决，先申请一个新的数组存储其所有值的2倍，排序，然后每一次取原数组中的值作为中间值进行查找，代码如下：

class Solution {
public:
     vector<long>::iterator find(vector<long>& tmp,long aim)
     {
         int a=0,b=tmp.size()-1;
         while(a<b)
         {
             int c=(a+b)/2;
             if(tmp[c]>aim)
                b=c-1;
             else if(tmp[c]<aim)
                a=c+1;
            else 
                return tmp.begin()+c;
         }
         return tmp.begin()+a;
     }
     int count(vector<long>& tmp,int a)
     {
         int begin=0,end=tmp.size()-1,middle;
         if(end<0)
            return 0;
         while(begin<end)
         {
             middle=(begin+end)/2;
             if(tmp[middle]<a)
                begin=middle+1;
             else
                end=middle;
         }
         if(tmp[begin]>=a) 
            return begin;
         else
            return tmp.size();
     }

    int reversePairs(vector<int>& nums) {
        int n=nums.size();
        vector<long >tmp(n,0);
        for(int i=0;i<n;i++)
            tmp[i]=(long )nums[i]*2L;
        int ans=0;
        sort(tmp.begin(),tmp.end());
        for(int i=0;i<n;i++)
        {
            long aim=(long)nums[i]*2L;
            vector<long>::iterator iter=find(tmp,aim);  
            tmp.erase(iter);
            ans+=count(tmp,nums[i]);

        }
        return ans;

    }
};

但是超时，所以参考已通过的代码，采用归并排序解决，以下为摘抄：

Just a mergesort solution, but using iterators (instead of indexes) and inplace_merge.

class Solution {
public:
    int sort_and_count(vector<int>::iterator begin, vector<int>::iterator end) {
        if (end - begin <= 1)
            return 0;
        auto mid = begin + (end - begin) / 2;
        int count = sort_and_count(begin, mid) + sort_and_count(mid, end);
        for (auto i = begin, j = mid; i != mid; ++i) {
            while (j != end and *i > 2L * *j)
                ++j;
            count += j - mid;
        }
        inplace_merge(begin, mid, end);
        return count;
    }

    int reversePairs(vector<int>& nums) {
        return sort_and_count(nums.begin(), nums.end());
    }
};