题解 | #数组中的逆序对#归并排序

数组中的逆序对

http://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5

采用归并排序的方法统计数组中逆序对的个数:
先对数组进行递归划分,划分为一个个的子数组,然后统计出相邻子数组之间的逆序对的数量,在统计逆序对的过程中,还需要对数组进行排序,这是为了防止在以后的统计过程中出现重复统计的情况以及计算逆序对的数目方便。

统计两个子数组之间的逆序对的数量的过程如下:
1、使用两个指针分别指向两个子数组的末尾,每次比较两个指针指向的数字。
(1)如果第一个子数组中的数字大于第二个子数组中的数字,则构成逆序对,逆序对的数目等于第二个子数组中指针左边剩余数字的个数。
(2)如果第一个子数组中的数字小于等于第二个子数组中的数字,则不构成逆序对。
2、每次比较的时候,都需要将较大的数字复制到辅助数组中,确保辅助数组中的元素是递增有序的。将较大的数字复制到辅助数组以后,其对应的指针和辅助数组的指针向前移动一个位置。
3、最后需要将辅助数组中的元素复制给原数组,否则将产生重复。

public class Solution {
    public int InversePairs(int [] array) {

        if (array == null || array.length == 0){
            return 0;
        }
        int[] temp = new int[array.length];
        return sort(array,temp,0,array.length - 1);
    }

    private int sort(int[] arr,int[] temp,int left,int right){

        if (left < right){

            int mid = (right - left) / 2 + left;
            int count = 0;
            count += sort(arr,temp,left,mid);
            count += sort(arr,temp,mid+1,right);


            // i 为左半部分的最后一个元素的下标
            int i = mid;
            // j 为右半部分的最后一个元素的下标
            int j = right;
            // t 为辅助数组的待存放元素位置的下标
            int t = right;

            while (i >= left && j >= mid + 1){

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

                    temp[t--] = arr[i--];
                    count = (count + j - mid)%1000000007;
                }else {

                    temp[t--] = arr[j--];
                }

            }

            while (i >= left){

                temp[t--] = arr[i--];
            }

            while (j >= mid + 1){

                temp[t--] = arr[j--];
            }

            t = right;

            while (right >= left){

                arr[right--] = temp[t--];
            }

            return count;
        }

        return 0;
    }
}
全部评论

相关推荐

04-25 19:29
已编辑
宁波大学 运营
被普调的六边形战士很高大:你我美牛孩
点赞 评论 收藏
分享
点赞 评论 收藏
分享
大厂的边缘业务去了也没啥用,也得不到任何成长,尤其是审核、中台这种价值产出不清楚的,别被大厂光环蒙蔽了双眼,如果你找实习工作,优先找"离钱近的业务",钱多的业务福利年终奖啥的都不会差的
陈100:呵呵。 你在大厂工作2年,后面准备好,可以随便跳很多公司。 去小厂,现在拿到所谓多的钱,有啥用啊,未来没有了。 而且应届生,工作没几年的,也不是赚钱的时间。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务