面试题51

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

示例 1:

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

限制：

• 0 <= 数组长度 <= 50000

Solutions

1. merge sort O(nlog(n))

class Solution {
public:
    int res = 0;
    vector<int> tmp;
    int reversePairs(vector<int>& nums) {
        tmp = vector<int>(nums.size() / 2 + 1);
        merge_sort(nums, 0, nums.size());
        return res;
    }
    void merge(vector<int> & nums, int lo, int mid, int hi) {
        copy(nums.begin() + lo, nums.begin() + mid, tmp.begin());
        int w = lo, i = 0, j = mid, maxi = mid - lo;
        while (i < maxi && j < hi) {
            if (nums[j] < tmp[i]) {
                res += maxi - i;
                nums[w++] = nums[j++];
            }
            else
                nums[w++] = tmp[i++];
        }
        while (i < maxi)
            nums[w++] = tmp[i++];
    }
    void merge_sort(vector<int> & nums, int lo, int hi) {
        if (hi - lo < 2) return;
        int mid = lo + ((hi - lo) >> 1);
        merge_sort(nums, lo, mid);
        merge_sort(nums, mid, hi);
        if (nums[mid - 1] > nums[mid])
            merge(nums, lo, mid, hi);
    }
};

Or a concise version

1. fenwick tree O(nlog(n) + nlog(n))

2. Denotes the position of an element in sorted array as rank.

3. Put the fenwick tree aside, the main idea behind this method is quite simple. For each element in array, the number of reversed pairs with this element as the smaller one equals to the number of elements with higer-rank rightward. Thus the answer of this problem can be calcualted by summing up counts of all numbers.

   • More specifically, Starting from an empty array(all values are set to 0), from back to front of the original aarry, we insert each element into this new array with it's proper position(True rank), then count the number of values inserted leftwards before.

   • This step cost O(n) time for each element, however, we can reduce it to log(n) by using fenwick tree.

4. Fenwick tree is a data structure can be used to efficiently query prefixsum of an array.

   • Insertion of an element is represented by increasing value by 1. Thus counting the number of values inserted equals to summing all values ahead.

// Fenwick Tree template
struct FenwickTree {
    vector<int> sums;
    FenwickTree(int n) : sums(n + 1) {}
    void update(int i, int delta) {
        while (i < sums.size()) {
            sums[i] += delta;
            i += lowbit(i);
        }
    }

    int query(int i) {
        int sum = 0;
        while (i > 0) {
            sum += sums[i];
            i -= lowbit(i);
        }

        return sum;
    }

    inline int lowbit(int x){
        return x & (-x);
    }
};

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        set<int> s(nums.begin(), nums.end());
        unordered_map<int, int> m;

        int rank = 1;
        while (!s.empty()) {
            m[*s.begin()] = rank++;
            s.erase(s.begin());
        }

        int numpair = 0;
        FenwickTree ft(rank - 1);
        // from back to front
        for (int i = nums.size() - 1; i >= 0; i--) {
            rank = m[nums[i]];
            ft.update(rank, 1);
            // number of elements with lower rank rightwards in the original array
            numpair += ft.query(rank - 1);
        }

        return numpair;
    }
};

or

struct FenwickTree {
    vector<int> sums;
    FenwickTree(int n) : sums(n + 1) {}
    void update(int n, int delta) {
        while (n < sums.size()) {
            sums[n] += delta;
            n += lowbit(n);
        }
    }
    int query(int n) {
        int sum = 0;
        while (n > 0) {
            sum += sums[n];
            n -= lowbit(n);
        }
        return sum;
    }
    inline int lowbit(int n) {
        return n & -n;
    }
};
class Solution {
public:
    inline int index(vector<int> & nums, int n) {
        return lower_bound(nums.begin(), nums.end(), n) - nums.begin();
    }
    int reversePairs(vector<int>& nums) {
        vector<int> sorted(nums);
        sort(sorted.begin(), sorted.end());
        sorted.resize(unique(sorted.begin(), sorted.end()) - sorted.begin());


        int res = 0, cnt = sorted.size();
        FenwickTree ft(cnt);
        for (auto n : nums) {
            int pos = index(sorted, n) + 1;
            res += ft.query(cnt) - ft.query(pos);
            ft.update(pos, 1);
        }

        return res;
    }
};