首页 > 试题广场 >

数组中的逆序对

[编程题]数组中的逆序对

热度指数：846830 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

数据范围：对于 $50\%$ 的数据, $size\leq 10^4$
对于 $100\%$ 的数据, $size\leq 10^5$

数组中所有数字的值满足 $0 \le val \le 10^9$

要求：空间复杂度 $O(n)$ ，时间复杂度 $O(nlogn)$

输入描述:

题目保证输入的数组中没有的相同的数字

示例1

输入

[1,2,3,4,5,6,7,0]

输出

示例2

输入

[1,2,3]

输出

算法知识视频讲解

一个优雅的程序猿

二分法，非暴力穷举。无敌的递归，爱你。

int InversePairs(int* nums, int numsLen ) {
    unsigned int res=0,i,j;
    if(numsLen<2)
        return 0;
    for(i=0;i<numsLen/2;i++) {
        for(j=0;j<(numsLen+1)/2;j++) {
            if((nums+numsLen/2)[j] < nums[i])
                res++;
        }
    }
    return (res+InversePairs(nums, numsLen/2)+InversePairs(nums+numsLen/2, (numsLen+1)/2))%1000000007;
}

编辑于 2024-03-16 10:45:13 回复(0)

小小小孩

static int ret = 0;
int* sort_arr = NULL;
void _merge_sort(int* data, int l, int mid, int r) {
    int start1 = l, end1 = mid-1, start2 = mid, end2 = r-1;
    int rcp=r-1;
    while (start1 <= end1 && start2 <= end2) {
        if (data[end1] > data[end2])
        {
            sort_arr[rcp--] = data[end1--];
            ret+=(end2-mid)+1;
            ret%=1000000007;
        }
        else
            sort_arr[rcp--] = data[end2--];
    }
    while (start1 <= end1)
        sort_arr[rcp--] = data[end1--];
    while (start2 <= end2)
        sort_arr[rcp--] = data[end2--];
    memcpy(data + l, sort_arr + l, (r - l)*sizeof(int));
}
void _InversePairs(int* data, int l, int r) {
    if (l + 1 >= r)
        return;
    int mid = (l + r) >> 1;
    _InversePairs(data, l, mid);
    _InversePairs(data, mid, r);
    _merge_sort(data, l, mid, r);
}
int InversePairs(int* data, int dataLen ) {
    // write code here
    ret = 0;
    sort_arr = malloc(sizeof(int) * dataLen);
    _InversePairs(data, 0, dataLen);
    if (sort_arr) {
        free(sort_arr);
        sort_arr = NULL;
    }
    return ret;
}

发表于 2023-06-14 16:00:25 回复(0)

帅奶哟。

int InversePairs(int* data, int dataLen ) {

// write code here

long int P = 0;

int i, j;

for(i = 0; i < dataLen; i++){

for(j = i+1; j < dataLen; j++){

if (data[i] > data[j]) P++;

}

printf("%d ",P);

return P%1000000007;

}

发表于 2023-03-15 09:46:08 回复(0)

JayneChou

#include <stdlib.h>
void merge(int *arr, int low, int high, int left, int right, long *p){
    int i = low, j = left, length = right - low + 1, index = 0;
    int *temp = (int*)malloc(sizeof(int) * length);
    while(i <= high && j <= right){
        if(arr[i] > arr[j]){
            temp[index++] = arr[j++];
            //这步变化是关键:首先进入merge的两部分数组已部分有序，所以如果arr[i] > arr[j]
            //那么arr[i+1],arr[i+2],...,arr[high]都大于arr[j],再把arr[j]存到temp里，
            //就没有遗漏
            *p += (high - i + 1);
        } else {
            temp[index++] = arr[i++];
        }
    }
    while(i <= high){
        temp[index++] = arr[i++];
    }
    while(j <= right){
        temp[index++] = arr[j++];
    }
    for(int k = 0; k < length; k++){
        arr[k + low] = temp[k];
    }
    free(temp);
 }
 void merge_Sort(int *arr, int low, int high, long *p){
    if(low < high){
        int middle = (low + high) / 2;
        merge_Sort(arr, low, middle, p);
        merge_Sort(arr, middle + 1, high, p);
        merge(arr, low, middle, middle + 1, high, p);
    } 
 }
int InversePairs(int* data, int dataLen ) {
    long count = 0;
    merge_Sort(data, 0, dataLen - 1, &count);
    return count % 1000000007;
}

发表于 2023-02-17 22:46:49 回复(0)

牛客722802822号

{
    // write code here
    unsigned int  tem=0;
    for (int i=0;i<dataLen-1;i++)
    {
        for(int j=i+1;j<dataLen;j++)
        {
            if(data[i]>data[j])
            {
                tem++;
            } 
        }
    }
    return tem%1000000007;
}

发表于 2022-11-15 21:02:30 回复(1)

取nm名字全被取了

int InversePairs(int* data, int dataLen ) 
{
    unsigned int count=0;
    for(int i=0;i<dataLen-1;i++)
    {
        for(int j=i;j<dataLen-1;j++)
        {
            if(data[i]>data[j+1])
            {
                count++;
            }
        }
    }
    return count%1000000007;
}

发表于 2022-11-05 15:08:46 回复(0)

尾上世莉架

static long long int count = 0;

void merge(int* data, int low, int mid, int high){
    int* temp = (int*)malloc(sizeof(int)*(high-low+1));
    int i = low, j = mid+1, k = 0;
    while(i<=mid && j<=high){
        if(data[i]<=data[j]){
            temp[k++] = data[i++];
        }else{
            temp[k++] = data[j++];
            count = count + mid - i + 1;
            // mid-i+1是排在j指向元素前面的更大元素的数量
        }
    }
    while(i<=mid) temp[k++] = data[i++];
    while(j<=high) temp[k++] = data[j++];
    for(k = 0, i = low;i<=high;) data[i++] = temp[k++];
}

void divide(int* data, int low, int high){
    if(high>low){
        int mid = (low+high)/2;
        divide(data, low, mid);
        divide(data, mid+1, high);
        merge(data, low, mid, high);
    }
}

int InversePairs(int* data, int dataLen ) {
    // write code here
    divide(data, 0, dataLen-1);
    return count % 1000000007;
}

发表于 2022-07-31 18:40:16 回复(0)

艾登皮洛斯

没看见能用的C实现，把官方的做了一下

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param data int整型一维数组 
 * @param dataLen int data数组长度
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
static int moder = 1000000007;

void Merging(int *data, int start, int mid, int end, int *sp){
    int tempdata[end-start+1];    //临时数组
    int c = 0;    //临时数组下标起点
    int s = start;    //保存在原数组的下标起点
    int l = start;    //左子数组的起始指针
    int r = mid + 1;    //
    
    while(l <= mid && r <= end){
        //当左子数组的当前元素小的时候，跳过，无逆序对
        if(data[l] <= data[r]){
            //放入临时数组
            tempdata[c] = data[l];    
            //临时数组下标+1
            c++;    
            // 左子数组指针右移
            l++;
        }
        else{ // 否则，此时存在逆序对
            // 放入临时数组
            tempdata[c] = data[r];
            // 逆序对的个数为    左子数组的终点- 当前左子数组的当前指针
            *sp += mid+1-l;
            *sp %= 1000000007;
            // 临时数组+1
            c++;
            // 右子数组的指针右移
            r++;
        }
    }
    // 左子数组还有元素时，全部放入临时数组
        while(l <= mid)
            tempdata[c++] = data[l++];
        // 右子数组还有元素时，全部放入临时数组
        while(r <= end)
            tempdata[c++] = data[r++];
        // 将临时数组中的元素放入到原数组的指定位置
        for(int num = 0; num<end-start+1; num++){
            data[s++] = tempdata[num];
        }
}

void Devising(int *data, int start, int end, int *s){    //在解决过程中，只有s是需要全程变动的
    int mid = start + (end-start)/2;    //求出中间值，作为二分基础
    if(start < end){
        Devising(data, start, mid, s);
        Devising(data, mid+1, end, s);
        Merging(data, start, mid, end, s);
    }
    
}

int InversePairs(int* data, int dataLen ) {
    // write code here
    int ss = 0;
    int *s = &ss;
    Devising(data, 0, dataLen-1, s);    //传入数组，数组起始，数组终止，逆序对数，开启递归
    return ss;
}

发表于 2022-07-23 22:55:55 回复(0)

莫小雨so

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param data int整型一维数组 
 * @param dataLen int data数组长度
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
static unsigned int count = 0;
void merge(int *arr, int lo, int mid, int hi);
void mergeSort(int *arr,int lo, int hi)
{
    if(lo == hi) return;
    int mid = (hi +lo) >> 1;
    mergeSort(arr, lo, mid);
    mergeSort(arr ,mid +1, hi);
    merge(arr,lo, mid, hi);
}
void merge(int *arr,int lo, int mid, int hi)
{
    int *B = (int*)malloc((mid - lo +1) * sizeof(int));
    int i,j,k;
    for(i = lo, j = 0; i <= mid; i++)
    {
        *(B + (j++)) = *(arr + i);
    }
    for(i = 0, k = lo, j = mid + 1;i <= mid - lo;)
    {
        if(*(B + i) > *(arr + j) && j <= hi)
        {
            count = count +(mid - lo - i + 1);
            *(arr + (k ++)) = *(arr + (j ++));
        }
        else
        {
            *(arr + (k ++)) = *(B + (i ++));
        }
        //*(arr + (k ++)) = *(B + i) < *(arr + j) || j > hi ? *(B + (i ++)) : *(arr + (j ++));
    }
    free(B);
    count = count % 1000000007;
}
int InversePairs(int* data, int dataLen ) {

    mergeSort(data, 0, dataLen - 1);
    return count;
}

发表于 2022-03-02 20:34:55 回复(0)

赶紧离职

int InversePairs(int* data, int dataLen ) {
    // write code here
    int i=0,j=0,P=0,k=0;
    for(i=0;i<dataLen;i++){
        for(j=i+1;j<dataLen;j++){
            if(data[i]>data[j]){P++;}
        }
        P=P%1000000007;
    }
    return P;
}

发表于 2021-11-16 13:18:24 回复(0)