数组中的逆序对_

Java

牛客384806710号

基于常规的归并排序，只在合并新数组的时候针对需要逆位的数据计算逆序步长

count += (mid - i + 1);

public class Solution {
    private static long count = 0;
    private static final int MOD = 1000000007;
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int InversePairs (int[] nums) {
        // write code here
        if(nums == null || nums.length < 2){
            return 0;
        }
        mergeSortCalc(nums, 0, nums.length - 1);
        return (int)(count % MOD);
    }

    public static void mergeSortCalc(int[] arr, int left, int right){

        if(left >= right){
            return;
        }

        int mid = left + (right - left)/2;
        mergeSortCalc(arr, left, mid);
        mergeSortCalc(arr, mid + 1, right);
        mergeArray(arr, left, mid, right);
    }

    private static void mergeArray(int[] arr, int left, int mid, int right){
        int[] temp = new int[right - left + 1];

        int i = left, j = mid + 1, k = 0;
        while(i <= mid && j <= right){
            if(arr[i] < arr[j]){
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
                // 核心：左半部分i到mid的所有元素都比arr[j]大，都是逆序对
                count += (mid - i + 1);
                count %= MOD; // 提前取模，避免数值溢出
            }
        }

        while(i <= mid){
            temp[k++] = arr[i++];
        }
        
        while(j<=right){
            temp[k++] = arr[j++];
        }

        for(int p = 0;p<temp.length;p++){
            arr[left + p] = temp[p];
        }
    }
}

发表于 2026-01-16 15:37:45 回复(0)

Java

靠谱六边形战士

这种方法算超小道吗......
public class Solution {

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

*

* @param nums int整型一维数组

* @return int整型

*/

public int InversePairs (int[] nums) {

// write code here

if (nums == null || nums.length == 0) {

return 0;

}

int count = 0;

List list = new ArrayList<Integer>();

// 存入优先级队列和列表型数组（方便元素操作）

PriorityQueue queue = new PriorityQueue<Integer>();

for (int i = 0; i < nums.length; i++) {

queue.offer(nums[i]);

list.add(nums[i]);

}

// 每次poll的元素是全局最小，查到它的下标，那么它前面的元素个数=下标=与其相关的逆序对个数(并且不需要和后面比较)，计算完后将元素从数组中移除

int polled = 0;

while (!queue.isEmpty()) {

polled = (int)queue.poll();

int index = list.indexOf(polled);

count = (count+index)%1000000007;

list.remove(index);

}

return count;

}

发表于 2025-09-16 22:48:58 回复(0)

Java

借来的猫不会遇见大反派

java用普通的归并排序顺便计算逆序对数
public class Solution {
    private static long count = 0;
    public int InversePairs (int[] nums) {
        // write code here
        count = 0;
        Sort(nums);
        return (int)(count % 1000000007);
    }
    public static  void Sort(int[] arr) {
        Sort(arr, 0, arr.length - 1);
    }
    public static  void Sort(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = l + (r - l) / 2;
        Sort(arr, l, mid);
        Sort(arr, mid + 1, r);
        if (arr[mid] > arr[mid + 1]) {
            merge(arr, l, mid, r);
        }
    }

    private static void merge(int[] arr, int l, int mid, int r) {
        int[] temp = Arrays.copyOfRange(arr, l, r + 1);
        int i = l, j = mid + 1;

        for (int k = l; k <= r; k++) {
            if (i > mid) {
                arr[k] = temp[j - l];
                j++;
            } else if (j > r) {
                arr[k] = temp[i - l];
                i++;
            } else if (temp[i - l]<temp[j - l]) {
                arr[k] = temp[i - l];
                i++;
            } else {
                arr[k] = temp[j - l];
                j++;
                count=count+(mid-i+1);
            }

        }
    }
}

发表于 2025-06-04 23:13:37 回复(0)

Java

金Main

import java.util.*;

public class Solution {

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

*

* @param nums int整型一维数组

* @return int整型

*/

public int InversePairs (int[] nums) {

long num = 0;

for(int i = 0;i < nums.length - 1;i++){

for(int j = i + 1;j < nums.length;j++){

if(nums[i] > nums[j]){

num++;

}

int count = (int)(num % 1000000007);

return count;

}

发表于 2025-04-28 15:50:09 回复(0)

Java

Sen🍓🍀

import java.util.*;

// @@@ 题解：归并排序
public class Solution {
    private int res = 0;
    private int mod = 1000000007;

    public int InversePairs (int[] nums) {
        // write your answer here
        mergeSort(nums, 0, nums.length - 1); // 归并排序
        // for (int i = 0; i < n; i++)  System.out.print(nums[i] + " ");
        return res;
    }

    // 归并排序
    private void mergeSort(int[] nums, int l, int r) {
        if (l == r) return;

        int mid = (l + r) / 2;
        mergeSort(nums, l, mid); // 分左半数组
        mergeSort(nums, mid + 1, r); // 分右半数组
        merge(nums, l, mid, r); // 合并
    }

    // 合并
    private void merge(int[] nums, int l, int mid, int r) {
        int[] a = new int[r - l + 1]; // 临时数组
        int i = l, j = mid + 1, k = 0;
        while (i <= mid && j <= r) {
            if (nums[i] > nums[j]) {
                res = (res + r - j + 1) % mod; // 逆序🍓【奥妙之处】
                a[k++] = nums[i++];
            } else {
                a[k++] = nums[j++];
            }
        }
        while (i <= mid)  a[k++] = nums[i++]; // 剩余的
        while (j <= r)  a[k++] = nums[j++];

        for (i = l, j = 0; i <= r; i++, j++) nums[i] = a[j]; // 复制到原数组
    }
}

发表于 2025-03-24 09:48:12 回复(0)

Java

西风东渐

    public static int InversePairs(int[] nums) {
        // write code here

        long res = 0;

        for (int i = 0; i < nums.length; i++) {

            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] > nums[j]) {
                    res++;
                }
            }
        }

        return (int) (res % 1000000007);
        
    }

发表于 2025-03-05 09:29:53 回复(0)

Java

牛客348570162号

// 暴力解法
    public int InversePairs1 (int[] nums) {
        long count = 0;
        for(int i=0;i<nums.length-1;i++){
            for(int j = i+1;j<nums.length;j++){
                if(nums[i] > nums[j]){
                    count++;
                }
            }
        }
        return (int)(count % 1000000007);
    }
    // 插入排序
    public int InversePairs2 (int[] nums) {
        long count = 0;
        ArrayList<Integer> list = new ArrayList<>();
        list.add(nums[nums.length-1]);
        for(int i=nums.length-2;i >= 0;i--){
            count += InversePairs_insert(list,nums[i]);
        }
        return (int)(count % 1000000007);
    }

    public int InversePairs_insert (ArrayList<Integer> list,int data) {
        int s=0,e=list.size()-1;
        int mid = 0;
        while(s<=e){
            mid = (s+e)/2;
            if(list.get(mid) == data){
                break;
            }else if(list.get(mid) > data){
                e = mid - 1;
            }else{
                s = mid + 1;
            }
        }
        if(s > mid){
            list.add(mid+1,data);
            return mid + 1;
        }else{
            list.add(mid,data);
            return mid;
        }
    }
    // 归并
    public int InversePairs (int[] nums) {
        if(nums.length < 2) return 0;
        int[] temp = new int[nums.length];
        int count = InversePairs_sort(nums,0,nums.length-1,temp);
        return count;
    }

    public int InversePairs_sort(int[] nums,int s,int e,int[] temp) {
        if(s >= e) return 0;
        int mid = (s+e)/2;
        int res = InversePairs_sort(nums,s,mid,temp) 
                + InversePairs_sort(nums,mid+1,e,temp);
        res = res % 1000000007;
        int i = s,j = mid+1;
        for(int k=s;k<=e;k++){
            temp[k] = nums[k];
        }
        for(int k=s;k<=e;k++){
            if(i == mid+1){
                nums[k] = temp[j++];
            }else if(j == e+1 || temp[i] <= temp[j]){
                nums[k] = temp[i++];
            }else{
                nums[k] = temp[j++];
                res += mid - i + 1;
            }
        }
        return res % 1000000007;
    }

发表于 2024-08-20 17:51:05 回复(0)

Java

人间水长东

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    public int InversePairs (int[] nums) {
        // write code here
        // 左程云老师讲过，通过归并排序过程中的左右两个字串的比较，可以实现逆序对的统计

        // 算法的时间复杂度O(NlogN)，空间复杂度O(N)

        // 调用归并排序的递归执行方法
        int count = process(nums, 0, (nums.length - 1));
        // 注意题目要求，对1000000007取模
        return count % 1000000007;
    }

    // 递归执行方法
    public int process(int[] nums, int l, int r) {
        // 递归出口
        if (l == r) {
            return 0;
        }
        // 计算中间索引
        int mid = (l + r) / 2;
        // 返回递归过程产生的逆序对数量
        int count = process(nums, l, mid) +
                    process(nums, mid + 1, r) +
                    compareAndMerge(nums, l, mid, r);
        // 注意题目要求，对1000000007取模
        return count % 1000000007;
    }

    // 比较与归并方法
    public int compareAndMerge(int[] nums, int l, int mid, int r) {
        // 记录逆序对的个数
        int count = 0;

        // 比较，归并
        int[] tempNums = new int[r - l + 1];
        // nums的左半区下标
        int leftIndex = l;
        // nums的右半区下标
        int rightIndex = mid + 1;
        // tempNums的下标
        int tempIndex = 0;
        while (leftIndex <= mid && rightIndex <= r) {
            // 请注意，归并排序merge的一个前提是，左右两个半区各自有序
            if (nums[leftIndex] < nums[rightIndex]) {
                // 左边 < 右边，则左边先进入tempNums中，leftIndex和tempIndex都++
                tempNums[tempIndex] = nums[leftIndex];
                leftIndex++;
            } else {
                // 左边 > 右边，则右边先进入tempNums中，rightIndex和tempIndex都++
                // 注意！此时算作逆序对！
                tempNums[tempIndex] = nums[rightIndex];
                rightIndex++;
                // tempNums[leftIndex]大，说明从leftIndex到mid上的数都更大，逆序数要全算上
                count += (mid - leftIndex + 1);
                // 注意题目要求，对1000000007取模
                count %= 1000000007;
            }
            tempIndex++;
        }
        // 此时退出了循环，要么leftIndex越界，要么rightIndex越界，以下两个while最多执行一个
        while (leftIndex <= mid) {
            // 右边的rightIndex先越界了，说明左边剩下的元素都比右边的大，把左边剩下的元素全部送进tempNums中
            // 注意！这里的逆序对已经被上一个while中考虑到了
            tempNums[tempIndex] = nums[leftIndex];
            leftIndex++;
            tempIndex++;
        }
        while (rightIndex <= r) {
            // 左边的leftIndex先越界了，说明右边剩下的元素都比左边的大，把右边剩下的元素全部送进tempNums中
            tempNums[tempIndex] = nums[rightIndex];
            rightIndex++;
            tempIndex++;
        }

        // 最后，把tempNums排好序的内容写回nums的对应位置
        for (int i = 0; i < tempNums.length; i++) {
            nums[l + i] = tempNums[i];
        }

        // 返回统计到的逆序数
        return count;
    }
}

发表于 2024-07-27 19:48:44 回复(0)

Java

WidHori

//这里用的是官方题解，我做了一些更详细的注释，希望可以帮到一些朋友

import java.util.*;

public class Solution {

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

*

* @param nums int整型一维数组

* @return int整型

*/

int mod = 1000000007;

public int mergeSort(int left, int right,int[] data,int[] temp) {

//将数组分开

if(left >= right) {

return 0;

}

int mid = (left + right) / 2;

int res = mergeSort(left,mid,data,temp) + mergeSort(mid + 1,right,data,temp);

//下面的代码本质上是将数组合并，并且排序，顺便给逆序对进行计数

res %= mod;

//两端数组

int i = left;//左边数组第一个元素

int j = mid + 1;//右边数组第一个元素

//将两段数组添加到一个临时数组中

for(int k = left; k <= right; k++) {

temp[k] = data[k];

}

for(int k = left; k <= right; k++) {

if(i == mid + 1) {//左边数组已经遍历完

data[k] = temp[j++];

}else if(j == right + 1 || temp[i] <= temp[j]) {//右边数组已经遍历完或者左边元素小于右边元素

data[k] = temp[i++];

}else {

data[k] = temp[j++];//左边元素大于右边元素，此时出现逆序对，进行计数

res += mid - i + 1;//res是下一层数组逆序对的结果，由于两边数组都是有序的，左边的某一个元素大于右边的某一个元素，那么左边后面的所有元素都比右边的哪一个元素大，因此要加上mid - i + 1

}

return res % mod;

}

public int InversePairs (int[] nums) {

// write code here

int left = 0;

int right = nums.length - 1;

int[] res = new int[right + 1];

return mergeSort(left,right,nums,res);

}

发表于 2024-03-20 22:09:52 回复(0)

Java

VXTW

终于过了，最后一个用例也太逆天了

public class Solution {
    public int InversePairs(int[] nums) {
        int left = 0, right = nums.length - 1;
        return (int)(mergeSort(nums, left, right) % 1000000007);
    }

    private long mergeSort(int[] nums, int left, int right) {
        if (left == right) {
            return 0;
        }
        int mid = left + ((right - left) >> 1);
        long x1 = mergeSort(nums, left, mid);
        long x2 = mergeSort(nums, mid + 1, right);
        long x3 = merge(nums, left, mid, mid + 1, right);
        return x1 + x2 + x3;
    }

    private long merge(int[] nums, int l1, int l2, int r1, int r2) {
        int[] temp = new int[r2 - l1 + 1];
        int i = 0;
        int l = l1;
        long count = 0;  
        while (l1 <= l2 && r1 <= r2) {
            if (nums[l1] > nums[r1]) {
                count = count + r2 - r1 + 1;
                temp[i++] = nums[l1++];
            } else {
                temp[i++] = nums[r1++];
            }
        }
        while (l1 <= l2) {
            temp[i++] = nums[l1++];
        }
        while (r1 <= r2) {
            temp[i++] = nums[r1++];
        }

        // 放回原来的数组
        i = 0;
        for (int i1 = l; i1 <= r2; i1++) {
            nums[i1] = temp[i++];
        }
        return count;
    }
}

发表于 2024-01-20 19:29:41 回复(1)

Java

serein_7

归并排序

public class Solution {
    public static final int MOD = 1000000007;

    public int InversePairs (int[] nums) {
        return mergeSort(nums, 0, nums.length - 1);
    }

    public int mergeSort(int[] nums, int l, int r) {
        if (l == r) {
            return 0;
        } 
        int mid = (l + r) >> 1;
        int lres = mergeSort(nums, l, mid);
        int rres = mergeSort(nums, mid + 1, r);

        int left = l, right = mid + 1, ans = (lres + rres) % MOD;
        int[] tmp = new int[r - l + 1];
        int idx = 0;
        while (left <= mid && right <= r) {
            if (nums[left] <= nums[right]) {
                tmp[idx++] = nums[left++];
            } else {
                tmp[idx++] = nums[right++];
                ans = (ans + mid - left + 1) % MOD;
            }
        } 
        while (left <= mid) tmp[idx++] = nums[left++];
        while (right <= r) tmp[idx++] = nums[right++];
        for (int i = 0; i < idx; i++) {
            nums[l + i] = tmp[i];
        }

        return ans;
    }
}

发表于 2023-11-11 15:11:11 回复(0)

Java

求知心态

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    public int InversePairs (int[] nums) {
        long total=0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j <nums.length; j++) {
                if (nums[i]>nums[j]){
                    total++;
                }
            }
        }
        return (int) (total%1000000007);
    }
}

发表于 2023-10-20 20:05:53 回复(2)

Java

dqxfz

// 归并排序，计算左边到右边的逆序对

public class Solution {

long n;

public int InversePairs (int[] nums) {

int[] tmp = new int[nums.length];

mergeSort(nums, tmp, 0, nums.length - 1);

return (int)(n % 1000000007);

}

public void mergeSort(int[] nums, int[] tmp, int l, int r) {

if (l < r) {

int c = (l + r) / 2;

mergeSort(nums, tmp, l, c);

mergeSort(nums, tmp, c + 1, r);

mergeAscend(nums, tmp, l, c, r);

}

private void mergeAscend(int[] nums, int[] tmp, int l, int c, int r) {

int l1 = l, r1 = c, l2 = c + 1, r2 = r;

int i = l1;

while (l1 <= r1 && l2 <= r2 ) {

if (nums[l1] <= nums[l2]) {

tmp[i++] = nums[l1++];

} else {

n += (r1 -l1 + 1);

tmp[i++] = nums[l2++];

}

while (l1 <= r1) {

tmp[i++] = nums[l1++];

}

while (l2 <= r2) {

tmp[i++] = nums[l2++];

}

for (i = l; i <= r; i++) {

nums[i] = tmp[i];

}

发表于 2023-09-16 21:39:41 回复(0)

Java

蚌埠住了的退堂鼓鼓手很不想上

import java.util.*;

public class Solution {

public int InversePairs(int [] array) {

long sum = 0;

for (int i = 1; i < array.length; i++) {

int values = array[i];

int[] ints = Arrays.copyOfRange(array, 0, i + 1);

Arrays.sort(ints);

int index = Arrays.binarySearch(ints, values);

sum += (i - index);

}

return (int)(sum % 1000000007);

}

发表于 2023-03-23 17:08:33 回复(1)

Java

BlueProtocol

通过率83.3%，不足是运行超时，代码没毛病。

public class Solution {
    public int InversePairs(int [] array) {
        if (array == null || array.length == 0) return -1;
        int count = 0;
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = i; j < array.length - 1; j++) {
                if (array[i] > array[j + 1])  count++;
            }
        }
        return count % 1000000007;
    }
}

发表于 2023-03-19 20:57:05 回复(2)

Java

小牛749

public class Solution {

int flag = 0;

public int InversePairs(int [] array) {

process(array,0,array.length-1);

return flag ;

}

public void process(int[] arr, int l, int r) {

if (l == r) {

return;

}

int m = l + ((r - l) >> 1);

process(arr, l, m);

process(arr, m + 1, r);

merge(arr, l, r);

}

public void merge(int[] arr, int left, int right) {

int mid = left + ((right - left) >> 1);

int[] temp = new int[right - left + 1];

int i = left;

int j = mid + 1;

int k = 0;

while (i <= mid && j <= right) {

if (arr[i] > arr[j]) {

temp[k++] = arr[j++]; //右边的小，小的加入辅助数组

flag+=mid-i+1; //右边的小说明有逆序对，因为每次两个部分都是排好序的所以arr[i]以及以后都比arr[j]大

flag %=1000000007;

}else {

temp[k++] = arr[i++];

}

if (i<=mid) {

int x = i;

while (i <= mid) {

temp[k++] = arr[i++];

}

flag += (mid-i+1)*(right-mid); //左边的多了说明在arr[i]以及以后都比右部分大所以这里乘了(right-mid)

flag %=1000000007;

}

while (j <= right) {

temp[k++] = arr[j++];

}

for (int i1 = 0; i1 < temp.length; i1++) {

arr[i1 + left] = temp[i1];

}

发表于 2023-03-16 22:13:36 回复(0)

Java

酷鹿路的跟屁虫

public class Solution {
    public int InversePairs(int [] array) {
        if(array.length == 0) return 0;
        long P =0L;
        for(int i =0; i < array.length - 1; i++)
            for(int j = i + 1; j < array.length; j++){
                if(array[i] > array[j]) P++;
            }
        return (int)(P % 1000000007);
    }
}

这个代码是不是时间复杂度是O（n^2）?虽然通过了，冒泡排序再怎么优化都是n^2吗？

发表于 2023-03-08 16:57:38 回复(1)

数组中的逆序对

输入描述:

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题