leetcode 493. Reverse Pairs 逆序对数量 + 归并排序做法

亦凉 2022-06-03 01:08 190阅读 0赞

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.

题意很简单，但是AC的方法不会，我觉得循环遍历也不错，虽然肯定会超时

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <cmath>
    
    using namespace std;
    
    class Solution 
    {
    public:
        int reversePairs(vector<int>& nums) 
        {
            int res = sort_and_count(nums.begin(), nums.end());
            return res;
        }
        int sort_and_count(vector<int>::iterator begin, vector<int>::iterator end) 
        {
            if (end - begin <= 1)
                return 0;
            else
            {
                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 && (*i) > 2L * (*j) )
                        ++j;
                    count += j - mid;
                }
                inplace_merge(begin, mid, end);
                return count;
            }
        }
    
    
        int reversePairsByLoop(vector<int>& nums)
        {
            int count = 0;
            for (int i = 0; i < nums.size(); i++)
            {
                for (int j = i + 1; j < nums.size(); j++)
                {
                    long long a = nums[i];
                    long long b = ((long long)nums[j]) << 1;
                    if (a > b)
                        count++;
                }
            }
            return count;
        }
    };

可以按照逆序对的做法来做，参考这个博客[剑指offer读书笔记：第五章，优化时间和空间效率][offer]

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    #include <cstdlib>
    #include <ctime>
    #include <array>
    using namespace std;
    
    
    class Solution
    {
    public:
        int reversePairs(vector<int>& a)
        {
            if (a.size() <= 0)
                return 0;
            vector<long long> all(a.begin(), a.end());
            return mergeSort(all, 0, all.size() - 1);
        }
    
        long long mergeSort(vector<long long>& a, int begin, int end)
        {
            if (begin == end)
                return 0;
            else
            {
                long long mid = (end - begin) / 2 + begin;
                long long leftCount = mergeSort(a, begin, mid);
                long long rightCount = mergeSort(a, mid + 1, end);
                long long midCount = 0;
                long long i = begin, j = mid + 1;
                while (i <= mid && j <= end)
                {
                    if (a[i] <= 2 * a[j])
                        i++;
                    else
                    {
                        midCount += (mid - i + 1);
                        j++;
                    }
                }
    
                vector<long long> tmp;
                i = begin, j = mid + 1;
                while (i <= mid && j <= end)
                {
                    if (a[i] <= a[j])
                        tmp.push_back(a[i++]);
                    else
                        tmp.push_back(a[j++]);
                }
                while (i <= mid)
                    tmp.push_back(a[i++]);
                while (j <= end)
                    tmp.push_back(a[j++]);
    
                for (int i = begin; i <= end; i++)
                    a[i] = tmp[i - begin];
                return leftCount + midCount + rightCount;
            }
        }
    };

[offer]: https://blog.csdn.net/jackzhang_123/article/details/79501029