逆序?qū)Χx

如果存在正整數(shù) $i,j$ 使得 $1\leq i<j\leq n$ 陷遮，而且 $A[i]>A[j]$ ，則 $<A[i],A[j]>$ 這個有序?qū)ΨQ為 $A$ 的一個逆序?qū)呀卜Q作逆序數(shù)拷呆。

例題1 - LeetCode劍指 Offer 51. 數(shù)組中的逆序?qū)?/h1>

題目

在數(shù)組中的兩個數(shù)字，如果前面一個數(shù)字大于后面的數(shù)字，則這兩個數(shù)字組成一個逆序?qū)Σ绺］斎胍粋€數(shù)組腰懂，求出這個數(shù)組中的逆序?qū)Φ目倲?shù)。

輸入: [7,5,6,4]

輸出: 5

限制：0 <= 數(shù)組長度 <= 50000

思路

逆序?qū)Γ?lt;7,5>,<7,6>,<7,4>,<5,4>,<6,4>

1. 暴力枚舉

數(shù)組中每個元素 $A[i]$ 與其后面每個元素 $A[j](j>i)$ 進(jìn)行比較项秉，若 $A[i]>A[j]$ 則逆序?qū)?shù)量加1绣溜。
時間復(fù)雜度： $O(n^2)$

2. 分治

若數(shù)組元素個數(shù)為0或1，則該數(shù)組逆序?qū)?shù)量為0娄蔼；若數(shù)組元素為有序怖喻，則該數(shù)組逆序?qū)?shù)量為0∷晁撸可以發(fā)現(xiàn)锚沸，逆序?qū)?shù)量其實就是將無序數(shù)組排為有序后，數(shù)組元素交換的次數(shù)涕癣。

使用分治算法哗蜈，遞歸將數(shù)組進(jìn)行二分（low ~ middle 和 middle+1 ~ high），直至為僅剩1個元素坠韩。此時逆序?qū)?shù)量為0距潘。再將數(shù)組（low ~ middle 和 middle+1 ~ high）兩兩依次合并，合并時若左半部分?jǐn)?shù)組中的元素 $A[i],(low\leq i\leq mid)$ 只搁，則逆序?qū)?shù)量增加 $mid-i+1$
以題目為例： $[7, 5, 6 ,4 ]$

逆序?qū)?jpg

時間復(fù)雜度：

O(nlog n)

具體代碼：

#include <bits/stdc++.h>
using namespace std;
vector<int> tmp;
long long int sum = 0;
long long int merge(vector<int> &nums,int low,int mid,int high){
    for (int i=low;i<=high;i++)
        tmp[i] = nums[i];
    int i = low;
    int j = mid+1;
    int k = low;
    while (i<=mid && j<=high){
        if (tmp[i]<=tmp[j])
            nums[k++] = tmp[i++];
        else {
            nums[k++] = tmp[j++];   
            sum += (mid-i+1);   
        }
    }
    while(i<=mid)
        nums[k++] = tmp[i++];
    while(j<=high)
        nums[k++] = tmp[j++];   
    return sum;
}

long long int mergeSort(vector<int> &nums,int low,int high){
    if (low == high)
        return 0;
    int mid=low+(high-low)/2;
    mergeSort(nums,low,mid);
    mergeSort(nums,mid+1,high);
    return merge(nums,low,mid,high);
}

int main(){
    int n,num;
    vector<int> nums;
    scanf("%d",&n);
    for (int i=0;i<n;i++){
        scanf("%d",&num);
        nums.push_back(num);
    }
    if (nums.size() < 2){
        cout << sum << endl;
        return 0;
    }
    tmp.resize(nums.size(),0);
    printf("%lld",mergeSort(nums,0,nums.size()-1));
    return 0;
}

例題2 - Count Inversion

Problem Description

Recall the problem of finding the number of inversions. As in the course, we are given a sequence of $n$ numbers $a_1,a_2,...a_n$ and we define an inversion to be a pair $i<j$ such that $a_i>a_j$
We motivated the problem of counting inversions as a good measure of how different two orderings are. However, one might feel that this measure is too sensitive. Let's call a pair a significant inversion if $i<j$ and $a_i>3a_j$ . Give an $O(nlog n)$ algorithm to count the number of significant inversions between two orderings.
The array contains N elements $(1 \leq N \leq 100,000)$ . All elements are in the range from 1 to 1,000,000,000.

Input

The first line contains one integer $N$ , indicating the size of the array. The second line contains $N$ elements in the array.
· 50% test cases guarantee that $N<100$

Output

Output a single integer which is the number of pairs of significant inversions.

Sample Inout

6
13 8 5 3 2 1

Sample Output

題意與例題1相同音比，只不過增加一個限定條件： $a_i>3a_j$ ，但此時使用分治算法后氢惋，將數(shù)組（low~middle 和 middle+1~high）兩兩依次合并時洞翩，合并時若左半部分?jǐn)?shù)組中的元素 $A[i],(low \leq i \leq mid)$ 大于右半部分?jǐn)?shù)組元素 $A[j],(mid+1 \leq j \leq high)$ ，且 $A[pos]>3A[j],(i \leq pos \leq mid)$ 則逆序?qū)?shù)量增加 $mid-pos+1$ 焰望。即骚亿，不能僅僅通過比較 $A[i],A[j]$ 就增加逆序?qū)?shù)量，如進(jìn)行 $[5,8,13]$ 和 $[2,3]$ 合并時柿估，雖然 $5<32$ 但是5后面的元素還存在大于3*2的元素循未，所以此時需要遍歷左半部分?jǐn)?shù)組陷猫，直至出現(xiàn)第一個大于三倍 $A[j]$ 的元素秫舌。因此需在原代碼基礎(chǔ)上進(jìn)行修改。

#include <bits/stdc++.h>
using namespace std;
vector<int> tmp;
long long int sum = 0;
long long int merge(vector<int> &nums,int low,int mid,int high){
    for (int i=low;i<=high;i++)
        tmp[i] = nums[i];
    int i = low;
    int j = mid+1;
    int k = low;
    while (i<=mid&&j<=high){
        if (tmp[i] <= tmp[j])
            nums[k++] = tmp[i++];
        else {
            int pos = i;
            while (pos <= mid){
                if (tmp[pos] > (long long)3*tmp[j]){//此處為了避免乘以3后超出范圍采用long long強(qiáng)制轉(zhuǎn)換绣檬。（OJ沒滿分就因為這足陨。）
                    sum += (mid-pos+1);
                    break;
                }
                pos++;
            }   
            nums[k++] = tmp[j++];   
        }
            
    }
    while(i<=mid)
        nums[k++] = tmp[i++];
    while(j<=high)
        nums[k++] = tmp[j++];   
    return con;
}

long long int mergeSort(vector<int> &nums,int low,int high){
    if (low == high)
        return 0;
    int mid = low+(high-low)/2;
    mergeSort(nums,low,mid);
    mergeSort(nums,mid+1,high);
    return merge(nums,low,mid,high);
}

int main(){
    int n,num;
    vector<int> nums;
    scanf("%d",&n);
    for (int i=0;i<n;i++){
        scanf("%d",&num);
        nums.push_back(num);
    }
    if (nums.size() < 2){
        cout << sum << endl;
        return 0;
    }
    tmp.resize(nums.size(),0);
    printf("%lld",mergeSort(nums,0,nums.size()-1));
    return 0;
}

【分治】逆序?qū)τ嬎?Count Inversion