【牛客】求数组中的逆序对-归并思想

本是古典何须时尚 2021-10-03 01:58 265阅读 0赞

有一组数，对于其中任意两个数组，若前面一个大于后面一个数字，则这两个数字组成一个逆序对。请设计一个高效的算法，计算给定数组中的逆序对个数。

给定一个int数组**A**和它的大小**n**，请返回A中的逆序对个数。保证n小于等于5000。

测试样例：

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

返回：7

解题思路：思路1：暴力搜索，n<5000。

思路2：在归并排序的过程中进行逆序对的整理计算，将比前面的数大于后面的数到mid的数的个数都加入进去。

import java.util.*;
    
    public class H {
        public int count(int[] A, int n) {
            // write code here
            if(A == null || n == 0)
                return 0;
            return mergesort(A,0,n-1);
        }
        public static int mergesort(int[]a,int l,int r){
            if(l == r)
                return 0;
            int mid = (l+r)/2;
            return mergesort(a,l,mid)+mergesort(a,mid+1,r)+merge(a,l,mid,r);
        }
        public static int merge(int []a,int left,int mid,int right){
            int [] temp = new int[right-left+1];
            int index = 0;
            int i = left;
            int j = mid + 1;
            int inverNum = 0;
            while(i<=mid && j<=right) {
                if (a[i] <= a[j])
                    temp[index++] = a[i++];
                else {
                    inverNum += (mid - i + 1);
                    temp[index++] = a[j++];
                }
            }
                while(i<=mid)
                    temp[index++] = a[i++];
                while(j<=right)
                    temp[index++] = a[j++];
                for(int k = 0;k<temp.length;k++)
                    a[left++] = temp[k];
            return inverNum;
        }
    }