BM20 数组中的逆序对

这篇具有很好参考价值的文章主要介绍了BM20 数组中的逆序对。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

描述

BM20 数组中的逆序对,java,算法,数据结构
解题思路:归并排序
分治:分治即“分而治之”,“分”指的是将一个大而复杂的问题划分成多个性质相同但是规模更小的子问题,子问题继续按照这样划分,直到问题可以被轻易解决;“治”指的是将子问题单独进行处理。经过分治后的子问题,需要将解进行合并才能得到原问题的解,因此整个分治过程经常用递归来实现。

具体做法:
1、这里要借助一个辅助数组,用来暂时存储合并后的结果。然后就开始进入划分阶段,把原数组从中间分开,直到子数组长度为1。
2、使用归并排序对原数组进行排序,并且统计逆序对,在这里设置两个指针i,j分别在左右子区间上移动,此时左区间的下标i都是小于右区间的,若知道了第一个大于a[j]的数,设为a[i],则左区间中a[i]以后的所有数,都比a[j]大。故此时,在左区间中,与a[j]构成逆序对的数字个数为左边剩下的数,剩余的数=(右端-左端+1)=(mid-i+1)。这个就是逆序对的计算方法。
3、将排好序的子序列合并,同时累加逆序对。

图解:
BM20 数组中的逆序对,java,算法,数据结构

代码:

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public 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;
        //i,j代表两个指针,分别在左右子区间上移动。
        int i = left,j = mid+1;
        for(int k=left;k<=right;k++){
            temp[k] = data[k]; //temp为辅助数组
        }
        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;
            }
        }
        return res%mod;

    }
    public int InversePairs (int[] nums) {
        // write code here
        int n = nums.length;
        int [] res = new int[n];
        return mergeSort(0,n-1,nums,res);
    }
}

个人疑问:不知道有没有和我一样的小伙伴,在看这道题的解题思路会有这样的疑问:为什么可以排序呢?这里题目要求的是在一个已经列好的数组中左边的数大于右边,才被称为逆序数,而如果使用归并排序的话,这个数组不是都有序了吗,有序的基础上找逆序,不是和题目违背了吗?

经过思考,我个人的见解是这样的,这里归并排序计算逆序对的数量和暴力解法不一样,暴力解法是在一个已有的数组中,对于每一个数,都判断其他的数是否比该数大,而递归排序,它比较的不是相邻的两个数,而是相邻的两个子数组,我认为这是看懂这道题的关键,因为比较的是两个子数组,所以在两个子数组中已经排好序是没关系的,因为两个子数组的相对顺序没有变,所以如果在左区间发现了一个比右区间大的数,那么说明左区间中这个数以后的数都会比右区间大,这是递归算法计算的公式。文章来源地址https://www.toymoban.com/news/detail-678095.html

到了这里,关于BM20 数组中的逆序对的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 剑指 Offer 51. 数组中的逆序对

    剑指 Offer 51. 数组中的逆序对   【归并】朴实无华的一个归并排序的应用,对于一个数组,我们通过归并排序来从大到小进行排序,在合并的过程中如果前面区间有比后面区间大的元素,那么后面区间从这个元素开始一直到结束都能和前面区间的那个数组成逆序对。 举个🌰

    2024年02月02日
    浏览(38)
  • 数据结构与算法中的七大排序(Java实现)

    目录 一、直接插入排序 二、希尔排序 三、直接选择排序 四、堆排序 五、冒泡排序 六、快速排序 七、归并排序               定义i下标之前的元素全部已经有序 ,遍历一遍要排序的数组,把i下标前的元素全部进行排序,当遍历玩这个数组后,就已经排好序了。        

    2024年02月06日
    浏览(58)
  • 【动态规划】【滑动窗口】【C++算法】 629K 个逆序对数组

    视频算法专题 动态规划汇总 C++算法:滑动窗口总结 逆序对的定义如下:对于数组 nums 的第 i 个和第 j 个元素,如果满足 0 = i j nums.length 且 nums[i] nums[j],则其为一个逆序对;否则不是。 给你两个整数 n 和 k,找出所有包含从 1 到 n 的数字,且恰好拥有 k 个 逆序对 的不同的数

    2024年01月17日
    浏览(44)
  • (排序) 剑指 Offer 51. 数组中的逆序对 ——【Leetcode每日一题】

    难度:困难 在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。 示例 1: 输入: [7,5,6,4] 输出: 5 限制 : 0 = 数组长度 = 50000 💡思路:归并排序 预备知识 「 归并排序 」是用 分治 思想,分

    2024年02月11日
    浏览(47)
  • JAVA经典百题之数组逆序输出

    要将一个数组逆序输出,即将数组中的元素顺序颠倒过来,可以使用多种方法。基本思路是创建一个新数组或修改原数组,将元素的顺序颠倒。 思路 创建一个新的数组,长度与原数组相同。 使用两个指针,一个指向原数组的起始位置,另一个指向新数组的末尾位置。 从原数

    2024年02月02日
    浏览(49)
  • java数据结构与算法刷题-----LeetCode1091. 二进制矩阵中的最短路径

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 双分裂蛇:是求二维表中从起点到终点的经典思路(也是求无权图的最短路径问题的经典解法)。创建两条分裂蛇,分别从起点和

    2024年04月26日
    浏览(52)
  • 数据结构与算法——20.B-树

    这篇文章我们来讲解一下数据结构中非常重要的B-树。 目录 1.B树的相关介绍 1.1、B树的介绍 1.2、B树的特点 2.B树的节点类 3.小结 在介绍B树之前,我们回顾一下我们学的树。 首先是 二叉树 ,这个不用多说,然后为了查找的效率,我们提出了 搜索二叉树(或者称为二叉搜索树

    2024年04月15日
    浏览(28)
  • 数据结构与算法(一): 稀疏数组

    在五子棋游戏或类似的游戏中,我们可以把整个棋盘想象成是一个有规律的二维数组,其值由0、1、2三个数字组成,0代表空白区域,1代表白子,2代表黑子。这种情况:即当一个数组中大部分元素为0或者为同一值时,存储该数组数据可以使用稀疏数组来对原始数组进行精简,

    2024年02月11日
    浏览(47)
  • 数据结构与算法 | 数组(Array)

    数组(Array)应该是最基础的数据结构之一,它由相同类型的元素组成的集合,并按照一定的顺序存储在内存中。每个元素都有一个唯一的索引,可以用于访问该元素。 数组索引(Index): 数组中的每个元素都有一个唯一的整数索引,从0开始计数。索引用于访问数组中的元素

    2024年02月08日
    浏览(51)
  • 用Java(C语言也可以看)实现冒泡排序和折半查找(详细过程图)+逆序数组

      目录 一、冒泡排序 1.冒泡排序介绍 2.排序的思路 3.完整代码 二、折半查找 1.折半查找介绍 2.查找的思路 3.完整代码 三、逆序数组 1.逆序思路 2..完整代码 冒泡排序是众多排序的一种,无论在C语言或者Java中都很常见,后续在数据结构中也会用到 1.冒泡排序介绍 (1)冒泡排

    2024年02月05日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包