最新公告
  • 欢迎您光临极客文库,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • 题目描述

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

    输入描述

    示例1

    输入

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

    输出

    7

    解题思路

    public class Solution {
        private long cnt = 0;
        private int[] tmp;  // 在这里声明辅助数组,而不是在 merge() 递归函数中声明
    
        public int InversePairs(int[] nums) {
            tmp = new int[nums.length];
            mergeSort(nums, 0, nums.length - 1);
            return (int) (cnt % 1000000007);
        }
    
        private void mergeSort(int[] nums, int l, int h) {
            if (h - l < 1)
                return;
            int m = l + (h - l) / 2;
            mergeSort(nums, l, m);
            mergeSort(nums, m + 1, h);
            merge(nums, l, m, h);
        }
    
        private void merge(int[] nums, int l, int m, int h) {
            int i = l, j = m + 1, k = l;
            while (i <= m || j <= h) {
                if (i > m)
                    tmp[k] = nums[j++];
                else if (j > h)
                    tmp[k] = nums[i++];
                else if (nums[i] < nums[j])
                    tmp[k] = nums[i++];
                else {
                    tmp[k] = nums[j++];
                    this.cnt += m - i + 1;  // nums[i] >= nums[j],说明 nums[i...mid] 都大于 nums[j]
                }
                k++;
            }
            for (k = l; k <= h; k++)
                nums[k] = tmp[k];
        }
    }
    
    本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
    极客文库 » 剑指Offer:数组中的逆序对

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    极客文库
    程序员的加油站

    Leave a Reply

    Hi, 如果你对这款模板有疑问,可以跟我联系哦!

    联系发布者

    Leave a Reply

    Hi, 如果你对这款模板有疑问,可以跟我联系哦!

    联系发布者
    • 99会员总数(位)
    • 3629资源总数(个)
    • 44本周发布(个)
    • 0 今日发布(个)
    • 105稳定运行(天)

    欢迎加入「极客文库」,成为原创作者从这里开始!

    立即加入 了解更多