面试题51. 数组中的逆序对

Tags: Hard Sort

Links: https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/

---

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

示例 1:

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

限制：

0 <= 数组长度 <= 50000

---

class Solution {
    int cnt;

public:
    int reversePairs(vector<int>& nums) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        cnt = 0;
        int n = nums.size();
        vector<int> tmp(n);
        mergeSort(nums, tmp, 0, n - 1);

        return cnt;
    }

    void merge(vector<int> & nums, vector<int> & tmp, int leftStart, int rightStart, int rightEnd)
    {
        int len = rightEnd - leftStart + 1;
        int pos = leftStart;
        int i = leftStart;
        int leftEnd = rightStart - 1;

        while (leftStart <= leftEnd && rightStart <= rightEnd) {
            if (nums[leftStart] <= nums[rightStart]) {
                tmp[pos++] = nums[leftStart++];
            }
            else {
                cnt += leftEnd - leftStart + 1;
                tmp[pos++] = nums[rightStart++];
            }
        }

        while (leftStart <= leftEnd) tmp[pos++] = nums[leftStart++];
        while (rightStart <= rightEnd) tmp[pos++] = nums[rightStart++];

        int count = 0;
        while (count++ < len) {
            nums[i] = tmp[i];
            ++i;
        }
    }

    void mergeSort(vector<int> & nums, vector<int> & tmp, int start, int end)
    {
        if (start < end) {
            int mid = start + ((end - start) >> 1);
            mergeSort(nums, tmp, start, mid);
            mergeSort(nums, tmp, mid + 1, end);
            merge(nums, tmp, start, mid + 1, end);
        }
    }
};

手写归并排序即可，或者手写线段树也可以。