数组中的逆序对(java实现和思路)

KLQ 2020-04-16 10:53:30 java常见问答 7193

下面的内容主要给大家分享的是数组中的逆序对的java实现以及思路,具体包含了3组实例,感兴趣的小伙伴可以来了解一下哦。

题目:

数组中的2个数字,假如,前面一个数字比后面的数字大,那么,这2个数字就组成一个逆序对。

输入1个数字,求出该数组当中的逆序对的总数P。

并且将P对1000000007取模的结果输出。 即输出P%1000000007。

输入:

数组中的逆序对

例:

输入:1,2,3,4,5,6,7,0

输出:7

思路1:

(1)暴力求解法,时间复杂度为o(n^2),空间复杂度o(1)

(2)使用归并排序的思想进行处理,时间复杂度o(nlog(n)),空间复杂度0(n)*/

代码实现:

class Solution
{
    public:
        int InversePairs(vector < int > data)
        {
            if (data.size() <= 1) return 0; //如果少于等于1个元素,直接返回0
            int * copy = new int[data.size()];
            //初始化该数组,该数组作为存放临时排序的结果,最后要将排序的结果复制到原数组中
            for (unsigned int i = 0; i < data.size(); i++)
                copy[i] = 0;
            //调用递归函数求解结果
            int count = InversePairCore(data, copy, 0, data.size() - 1);
            delete[] copy; //删除临时数组
            return count;
        }
    //程序的主体函数
    int InversePairCore(vector < int > & data, int * & copy, int start, int end)
    {
        if (start == end)
        {
            copy[start] = data[start];
            return 0;
        }
        //将数组拆分成两部分
        int length = (end - start) / 2; //这里使用的下标法,下面要用来计算逆序个数;也可以直接使用mid=(start+end)/2
        //分别计算左边部分和右边部分
        int left = InversePairCore(data, copy, start, start + length) % 1000000007;
        int right = InversePairCore(data, copy, start + length + 1, end) % 1000000007;
        //进行逆序计算
        int i = start + length; //前一个数组的最后一个下标
        int j = end; //后一个数组的下标
        int index = end; //辅助数组下标,从最后一个算起
        int count = 0;
        while (i >= start && j >= start + length + 1)
        {
            if (data[i] > data[j])
            {
                copy[index--] = data[i--];
                //统计长度
                count += j - start - length;
                if (count >= 1000000007) //数值过大求余
                    count %= 1000000007;
            }
            else
            {
                copy[index--] = data[j--];
            }
        }
        for (; i >= start; --i)
        {
            copy[index--] = data[i];
        }
        for (; j >= start + length + 1; --j)
        {
            copy[index--] = data[j];
        }
        //排序
        for (int i = start; i <= end; i++)
        {
            data[i] = copy[i];
        }
        //返回最终的结果
        return (count + left + right) % 1000000007;
    }
};

思路2

代码实现:

public class Solution
{
    int cnt;
    public int InversePairs(int[] array)
    {
        cnt = 0;
        if (array != null)
            mergeSortUp2Down(array, 0, array.length - 1);
        return cnt;
    }
    /*
     * 归并排序(从上往下)
     */
    public void mergeSortUp2Down(int[] a, int start, int end)
    {
        if (start >= end)
            return;
        int mid = (start + end) >> 1;
        mergeSortUp2Down(a, start, mid);
        mergeSortUp2Down(a, mid + 1, end);
        merge(a, start, mid, end);
    }
    /*
     * 将一个数组中的两个相邻有序区间合并成一个
     */
    public void merge(int[] a, int start, int mid, int end)
    {
        int[] tmp = new int[end - start + 1];
        int i = start, j = mid + 1, k = 0;
        while (i <= mid && j <= end)
        {
            if (a[i] <= a[j])
                tmp[k++] = a[i++];
            else
            {
                tmp[k++] = a[j++];
                cnt += mid - i + 1; // core code, calculate InversePairs............
            }
        }
        while (i <= mid)
            tmp[k++] = a[i++];
        while (j <= end)
            tmp[k++] = a[j++];
        for (k = 0; k < tmp.length; k++)
            a[start + k] = tmp[k];
    }
}

思路3:

这道题,是归并排序的典型应用。

归并排序的基本思想是分治,在治的过程中有前后数字的大小对比,这个时候就是统计逆序对的最佳时机。

代码实现:

public class Solution
{
    //统计逆序对的个数
    int cnt;
    public int InversePairs(int[] array)
    {
        if (array.length != 0)
        {
            divide(array, 0, array.length - 1);
        }
        return cnt;
    }
    //归并排序的分治---分
    private void divide(int[] arr, int start, int end)
    {
        //递归的终止条件
        if (start >= end)
            return;
        //计算中间值,注意溢出
        int mid = start + (end - start) / 2;
        //递归分
        divide(arr, start, mid);
        divide(arr, mid + 1, end);
        //治
        merge(arr, start, mid, end);
    }
    private void merge(int[] arr, int start, int mid, int end)
    {
        int[] temp = new int[end - start + 1];
        //存一下变量
        int i = start, j = mid + 1, k = 0;
        //下面就开始两两进行比较,若前面的数大于后面的数,就构成逆序对
        while (i <= mid && j <= end)
        {
            //若前面小于后面,直接存进去,并且移动前面数所在的数组的指针即可
            if (arr[i] <= arr[j])
            {
                temp[k++] = arr[i++];
            }
            else
            {
                temp[k++] = arr[j++];
                //a[i]>a[j]了,那么这一次,从a[i]开始到a[mid]必定都是大于这个a[j]的,因为此时分治的两边已经是各自有序了
                cnt = (cnt + mid - i + 1) % 1000000007;
            }
        }
        //各自还有剩余的没比完,直接赋值即可
        while (i <= mid)
            temp[k++] = arr[i++];
        while (j <= end)
            temp[k++] = arr[j++];
        //覆盖原数组
        for (k = 0; k < temp.length; k++)
            arr[start + k] = temp[k];
    }
}

希望以上的三种实现方式可以对你有所帮助,请继续关注本站,有更多的Java实例,可以分享给大家。