本文共 1759 字，大约阅读时间需要 5 分钟。

2.4 Inversions

Let A[1...n]be an array of n distinct numbers. If i < j and A[i] > A[j], then thepair(i, j)is called an inversion of A.Give an algorithm that determines the number of inversions in any permutationon n elements in O(nlgn) worst-case time. (Hint: Modify merge sort.)

Thinking: We may think both A[i…j] and A[j+1…k] are sorted subarray of A (0 <= i < j < k <= n). if A[x](i<=x<=j) is bigger than A[j+1], then all numbers behind A[x] are bigger than A[j+1], so there are j-x+1 inversions bigger than A[j+1].

class Solution {public:    int getInversionNumbers(vector
   
    & data, int begin, int end) {        if (begin < end - 1) {            int middle = (begin + end - 1) / 2;            int left = solute(data, begin, middle + 1);            int right = solute(data, middle + 1, end);            return findAndSort(data, begin, middle + 1, end) + left + right;        }        return 0;    }private:    int findAndSort(vector
    
     & data, int start, int middle, int end) {        vector
     
       left(data.begin() + start, data.begin() + middle);        vector
      
        right(data.begin() + middle, data.begin() + end);        int i = 0, j = 0, k = start;        int count = 0;        while (i < left.size() && j < right.size()) {            if (left[i] > right[j]) {                // If current item in left bigger than the the current item of right,                // then all items after current left item is bigger than the left.                count += left.size() - i;                data[k++] = right[j++];            } else {                data[k++] = left[i++];            }        }        while (i < left.size()) data[k++] = left[i++];        while (j < right.size()) data[k++] = right[j++];        return count;    }};
      
     
    
   

转载地址：http://unlsi.baihongyu.com/