51_剑指offer_java_数组中的逆序对_java实现数组的逆序队个球,复杂度不超过nlogn-程序员宅基地

技术标签: 面试算法题  

目录

 

题目描述

测试用例

题目考点

解题思路

参考解题

归并排序


题目描述

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。例如数组{7, 5, 6, 4}中,一共存在5个逆序对,分别是(7, 6)、(7, 5)、(7, 4)、(6, 4)、(5, 4)。

 

测试用例

  • 功能测试(输入未经排序的数组、递增排序的数组、递减排序的数组;输入的数组中包含重复的数字)
  • 边界值测试(输入的数组中只有两个数字;输入的数组只有一个数字)
  • 特殊输入测试(表示数组的指针为空指针)

 

题目考点

  • 考察应聘者分析复杂问题的能力。
  • 考察应聘者对归并排序的掌握程度。

 

解题思路

实质上,利用归并排序实现,时间复杂度为O(nlogn),空间复杂度O(n);

1、先把数组分隔成子数组,分别统计子数组内部  + 相邻子数组之间 的逆序对;

2、在统计逆序对的时候,对子数组排序。

 

如数组{7, 5, 6, 4}中

  1. 把长度为4的数组分解成两个长度为2的子数组;
  2. 把长度为2的数组分解成两个成都为1的子数组;
  3. 把长度为1的子数组合并、排序并统计逆序对,得到(7, 5)、(6, 4);
  4. 把长度为2的子数组合并、排序并统计逆序对,得到(7, 6)、(7, 4)、(5, 4);

 

参考解题

public class Solution {
    // 归并排序
    
    public int InversePairs(int [] array) {
        // 异常
        if(array == null || array.length < 0){
            return 0;
        }
        // 辅助数组
        int[] temp = new int[array.length];
        for(int i = 0; i < array.length; ++i ){
            temp[i] = array[i];
        }
        
        int count = mergeSort(array, temp, 0, array.length - 1);
        return count;
    }
    
    // 归并排序
    public int mergeSort(int[] array, int[] temp, int low, int high){
        // 异常
        if(low == high){
            return 0;
        }
        
        int mid = (low + high) >> 1;
        // -------子数组内部---------------------------------------------
        int left = mergeSort(array, temp, low, mid) % 1000000007;
        int right = mergeSort(array, temp, mid + 1, high) % 1000000007;
        // -------子数组之间---------------------------------------------
        int count = 0;
        // 子数组左边最右端下标
        int i = mid;
        // 子数组右边最右端下标
        int j = high;
        // 辅助数组最右端下标
        int k = high;
        
        while(i >= low && j >= mid + 1){
            if(array[i] > array[j]){
                temp[k--] = array[i--];
                count += j - mid;
                if(count >= 1000000007)//数值过大求余
                {
                    count %= 1000000007;
                }
            }else{
                temp[k--] = array[j--];
            }
        }
        // 如果左边有剩余元素,移入辅助数组
        for(; i >= low ; --i){
            temp[k--] = array[i];
        }
        // 如果右边有剩余元素,移入辅助数组
        for(; j >= mid + 1 ; --j){
            temp[k--] = array[j];
        }
        // 临时数组覆盖原数组???
        System.arraycopy(temp, low, array, low, high - low + 1);
        
        // 子数组内部 + 子数组之间
        return (left + right + count) % 1000000007;
    }
    
}

 

归并排序

https://blog.csdn.net/weixin_41582192/article/details/81239266?utm_source=distribute.pc_relevant.none-task

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Longtermevolution/article/details/104394987

智能推荐

后端学习路线-程序员宅基地

文章浏览阅读156次。https://link.zhihu.com/?target=https%3A//github.com/AobingJava/JavaFamily针对后端的学习,可以参照以上的网址来进行学习。后端的话就是搞一些和数据库相关的内容。其实也不是很难。然后前端+后端一起搞的人叫做全栈工程师。这里后端学习路线就分享到这里。毕竟我可能不是这方面的高手,大家想要自己加餐的,就在网上进行资料搜集和整合即可。...

OpenCV学习笔记(一):opencv安装,边缘提取_opencv 提取地面和墙面-程序员宅基地

文章浏览阅读400次。OpenCV学习笔记记录了本人在图像处理相关学习过程中对opencv的使用心得,主要是供自己复习,但如果碰巧为你解决了问题,那就更好了。如有错误,欢迎指正。一、OpenCV的安装安装opencv可以去官网下载对应版本的包。一些朋友可能会碰到网络问题导致下载速度特慢,此处我为大家提供opencv4.1.2资源与opencv4.1.2 Tutorial离线包。具体的安装过程建议参考:VS2017配置opencv,这个教程很详细,亲测很多次可用。..._opencv 提取地面和墙面

java中nextLine(),读取换行符的解决_in.nextline();、-程序员宅基地

文章浏览阅读3.7k次,点赞9次,收藏12次。一:问题描述当输入完第一值后,就未能输入后来的字符串package com.wyj.two;import java.util.Scanner;public class text { public static void main(String[] args) { Scanner in = new Scanner(System.in); int temp = in.nextInt(); System.out.println(temp); _in.nextline();、

Modem Router-程序员宅基地

文章浏览阅读377次。Modem调制解调器 router 路由器192.168.1.1 192.168.1.1由于天翼宽带的光猫(modem)信号真心不行,自己加了一个TP-LINK路由器1)访问硬件设备modem地址就是192.168.1.1,无线网络ID:2)访问硬件设备Router地址也是192.168.1.1我要用笔记本连接路由器的...

data = json.load(jsonfile) 报错_data = json.load(file)-程序员宅基地

文章浏览阅读1.1k次。data = json.load(jsonfile) 报错json.decoder.JSONDecodeError: Expecting value如何解决?import jsonjsonfile = open('example.json')data = json.load(jsonfile)print(data['string'])代码本身并没有问题,主要是斜体样式定义的数据exam..._data = json.load(file)

绕过disable_functions_蚁剑disable_function bypass-程序员宅基地

文章浏览阅读2k次。文章目录前言黑名单绕过利用 LD_PRELOAD 环境变量LD_PRELOAD 简介利用条件劫持 getuid()劫持启动进程演示过程利用ShellShock(CVE-2014-6271)使用条件:原理简述演示过程php-json-bypass使用条件:原理简述利用脚本演示过程php-GC-bypass使用条件:原理简述利用脚本演示过程利用 Backtrace使用条件:原理简述利用脚本利用方法利用 Apache Mod CGI使用条件:原理简述演示过程2020De1CTF通过攻击 PHP-FPM理论:ctf_蚁剑disable_function bypass

随便推点

python 计算ssim_ssim python计算-程序员宅基地

文章浏览阅读911次。python 计算ssim_ssim python计算

人物识别的学习笔记_人物分类规则集-程序员宅基地

文章浏览阅读261次。1 人物分类的数据集自己制作数据集;_人物分类规则集

Excel 2010 受保护的工作表中使用“组合”功能(亲自实践)-程序员宅基地

文章浏览阅读1.4w次。组合功能在Excel中经常使用,可以很方便地将一组数据展开或者折叠当我们需要将其所在工作表进行保护时,发现之前设定的组合无法使用了 此时,就需要我们在VBA中设定相关语句:PS:该方法转自Excelhome论坛 (http://club.excelhome.net/forum.php?mod=viewthread&tid=259467) Private Sub Workbo

DB2基本概念——实例,数据库,模式,表空间_db2クライアント-程序员宅基地

文章浏览阅读4.3k次,点赞3次,收藏13次。DB2支持以下两种类型的表空间:&nbsp;&nbsp; &nbsp; 1、 系统管理存储器表空间(SMS-SYSTEM&nbsp;&nbsp; MANAGED&nbsp;&nbsp; STORAGE)&nbsp;&nbsp; &nbsp; 2、 数据库管理存储器表空间(DMS-DATABASE&nbsp;&nbsp; MANAGED&nbsp;&nbsp; STORAGE)&nbsp;&_db2クライアント

shell脚本部署apache_编写脚本完成本机apache部署-程序员宅基地

文章浏览阅读348次。shell脚本一键部署Apache服务1.进入/opt目录下创建apache目录,然后创建一个脚本文件和一个存放安装的目录2.下载好apache服务所需要的安装包3.编写apache脚本4.验证效果1.进入/opt目录下创建apache目录,然后创建一个脚本文件和一个存放安装的目录[root@localhost opt]# lsapache[root@localhost opt]# cd apache/[root@localhost apache]# lsinstall.sh soft[ro_编写脚本完成本机apache部署

编译技术-优化理论-程序员宅基地

文章浏览阅读1.2k次。这是我们学的第一个全局数据流分析,但是只能说教材封装得太好了。肯定这些分析是全局数据流分析,但是以基本块为颗粒度是怎么一回事?即使分析出了基本块的 in 或者 out,对于实际的改写程序并没有办法起到指导意义,这是因为改写的颗粒度是指令级的。显然一个粗粒度的分析没办法指导一个细粒度的改写。进行块级颗粒度的数据流分析,这个部分具有全局性质,会统筹考虑 CFG 的数据流向问题。在每个块内进行指令级颗粒度的数据流分析,这个部分发生在局部,利用的是块级颗粒度分析的结果,不需要考虑全局信息。_编译技术

推荐文章

热门文章

相关标签