【剑指Offer】T51 数组中的逆序对

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组, 求出这个数组中的逆序对的总数 P。并将 P 对 1000000007 取模的结果输出。 即输出 P%1000000007

输入描述:

题目保证输入的数组中没有的相同的数字数据范围:    对于%50的数据,size<=10^4    对于%75的数据,size<=10^5    对于%100的数据,size<=2*10^5

思路 1:归并排序思想,其实就是调整逆序对的过程。可以描述为:分组到最小(两个一组),然后调整逆序对。合并成四个再调整逆序对直到合并成原始数组。所以在这个过程中的调整次数即逆序对的个数。O(nlog2n)

先默写一遍归并排序:

// 归并过程
void merge(int A[], int low, int mid, int high){
    int help[high - low + 1]; // 辅助数组(保护现场,以便后面继续,整个做完后再赋给原数组对应的部分)
    int i = 0;
    int lowIndex = low;
    int highIndex = mid + 1;
    
    while(lowIndex <= mid && highIndex <= high){
        if(A[lowIndex] < A[highIndex])
            help[i++] = A[lowIndex++];
        else
            help[i++] = A[highIndex++];
    }
    
    //左边和右边肯定有一边到头了,不可能同时,因为每次只移动一边
    while(lowIndex <= mid)
        help[i++] = A[lowIndex++];
    while(highIndex <= high)
        help[i++] = A[highIndex++];
    
    //将排好序的辅助数组赋值给原始数组,不需要返回值
    for(int i = 0; i < high-low+1; i++){
        A[low+i] = help[i];
    }
}

//递归
void mergeSort(int A[], int low, int high){
    if(low == high)
        return;
    
    int mid = low + (high-low)/2;
    
    // 左部分归并排序
    mergeSort(A, low, mid);
    // 右部分归并排序
    mergeSort(A, mid+1, high);
    // 左右部分归并
    merge(A, low, mid, high);
}

//重写, 归并整个数组
void mergeSort(int A[], int n){
    if(A == NULL || n < 2)
        return;
    mergeSort(A, 0, n-1);
}

int main(){
    int n; 
    while(cin >> n){
        int arr[n];
        for(int i = 0; i < n; i++) cin >> arr[i];
 
        mergeSort(arr, n);
 
        for(int i = 0; i < n; i++){
            cout << arr[i] << " ";
        } 
        cout << endl;
    }
    return 0;
} 

Vector 版:

#include <iostream>
#include <stdio.h>
#include <vector>
#include <map>
#include <stack>
#include <queue>
using namespace std;

void merge(vector<int>& A, int low, int mid, int high){
    int i = 0;
    
    int help[high - low + 1];
    int lowIndex = low;
    int highIndex = mid + 1;
    
    while (lowIndex <= mid && highIndex <= high) {
        if(A[lowIndex] <= A[highIndex])
            help[i++] = A[lowIndex++];
        else
            help[i++] = A[highIndex++];
    }
    
    while (lowIndex <= mid)
        help[i++] = A[lowIndex++];
    
    while (highIndex <= high)
        help[i++] = A[highIndex++];
    
    for (int i = 0; i < high-low+1; i++) {
        A[low+i] = help[i];
    }
}

void mergeSort(vector<int>& A, int low, int high){
    if(low == high)
        return;
    
    int mid = low + (high-low)/2;
    printf("%d\n", A[mid]);
    mergeSort(A, low, mid);
    mergeSort(A, mid+1, high);
    merge(A, low, mid, high);
}

void mergeSort(vector<int>& A){
    int n = A.size();
    if(A.empty() || n < 2)
        return;
    
    mergeSort(A, 0, n-1);
}

void PrintArr(vector<int> arr){
    for (int i = 0; i < arr.size(); i++) {
        if(i == arr.size()-1)
            cout<<arr[i]<<endl;
        else
            cout<<arr[i]<<", ";
    }
}

void PrintArr(int arr[], int n){
    for (int i = 0; i < n; i++) {
        if(i == n-1)
            cout<<arr[i]<<endl;
        else
            cout<<arr[i]<<", ";
    }
}

int main() {
    vector<int> A = {6, -3, -2, 7, -15, 1, 2, 2};
    mergeSort(A);
    PrintArr(A);
    
    return 0;
}

// 未完待续

思路 2:树状数组

本文链接:https://ariser.cn/index.php/archives/406/
本站文章采用 知识共享署名4.0 国际许可协议进行许可,请在转载时注明出处及本声明!