【Java 优选算法】分治-归并排序

欢迎关注个人主页:逸狼


创造不易,可以点点赞吗~

如有错误,欢迎指出~



数组分块如二叉树的前序遍历, 而归并排序就如二叉树的后序遍历 

912. 排序数组

解法

使用归并算法

  1. 根据中间点划分区间, mid =(right + left ) / 2
  2. 将左右区间排序
  3. 合并两个有序数组
  4. 处理没有遍历完的数组
  5. 将排好序的数组tmp覆盖到原数组nums里

优化: 将tmp数组new成一个全局变量,减少频繁的空间开销

代码

class Solution {int[] tmp;public int[] sortArray(int[] nums) {int n = nums.length;tmp = new int[n];mergeSort(nums, 0, n - 1);return nums;}public void mergeSort(int[] nums, int left, int right){if(left >= right) return;//1.找到中间点midint mid = (left + right) / 2;//2.左右排好序mergeSort(nums, left, mid);mergeSort(nums, mid + 1, right);//3.合并有序数组 [left, mid] [mid + 1, right]int cur1 = left, cur2 = mid + 1, i = 0;while(cur1 <= mid && cur2 <= right){tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];}//处理没有遍历完的数组while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= right) tmp[i++] = nums[cur2++];//4.tmp覆盖numsfor(int j = left; j <= right; j++){nums[j] = tmp[j - left];}}
}

LCR 170. 交易逆序对的总数(数组中的逆序对)

解法

解法一: 暴力枚举: 两层for循环

解法二: 分治,N*logN

将数组通过mid分为两部分,

  1. 先找左半部分的逆序对, 再左排序
  2. 再找右半部分的逆序对, 再右排序
  3. 最后找一左一右组合的逆序对(此时左数组和右数组分别都是有序的),再合并排序

策略一: 找出该数(nums[cur1] )之前,有多少个(mid - cur2 + 1)数比我(nums[cur2] )大.

  • 当nums[cur1] <= nums[cur2] 时 , cur1++;
  • 当nums[cur1] > nums[cur2]时 ,ret += mid - cur1 + 1, cur2++

策略二: 找出该数(nums[cur1] )之后,有多少个(right - cur2 + 1)数比我(nums[cur2] )小.

  • 当nums[cur1] <= nums[cur2] 时 , cur2++;
  • 当nums[cur1] > nums[cur2]时 ,ret += right - cur2 + 1, cur1++

  • 时间复杂度:O(nlogn),这是归并排序的时间复杂度,其中 n 是数组的长度。
  • 空间复杂度:O(n),主要是临时数组 tmp 的空间开销。

代码

class Solution {int[] tmp;public int reversePairs(int[] nums) {int n = nums.length;tmp = new int[n];return merge(nums, 0, n - 1);}public int merge(int[] nums, int left, int right){if(left >= right) return 0;//找出中间点midint mid = (left + right) / 2;int ret = 0;//左右排好序,返回结果ret += merge(nums, left, mid);ret += merge(nums, mid + 1, right);//合并有序数组,计算一左一右逆序对int cur1 = left, cur2 = mid + 1, i = 0;while(cur1 <= mid && cur2 <= right){if(nums[cur1] <= nums[cur2]){tmp[i++] = nums[cur1++];}else{ret += mid - cur1 + 1;tmp[i++] = nums[cur2++];}}//处理剩下的数组while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= right) tmp[i++] = nums[cur2++];for(int j = left; j <= right; j++){nums[j] = tmp[j - left];}return ret;}
}

315. 计算右侧小于当前元素的个数

解法

解法: 归并排序

和上一题类似,但是这里只能通过策略二: 降序解决

注意: 最终结果是加在原始数组的下标中 

代码

class Solution {int[] ret;int[] index; //标记 nums中当前元素的原始下标int[] tmpIndex;int[] tmpNums;public List<Integer> countSmaller(int[] nums) {int n = nums.length;ret = new int[n];index = new int[n];tmpIndex = new int[n];tmpNums = new int[n];//初始化index数组for(int i = 0; i < n; i++){index[i] = i;}merge(nums, 0, n - 1);List<Integer> l = new ArrayList<>();for(int x : ret){l.add(x);}return l;}public void merge(int[] nums, int left, int right){if(left >= right) return;int mid = (left + right) / 2;merge(nums, left, mid);merge(nums, mid + 1, right);//[left, mid] [mid + 1, right] 处理一左一右的情况int cur1 = left, cur2 = mid + 1, i = 0;while(cur1 <= mid && cur2 <= right){//降序排列if(nums[cur1] <= nums[cur2]){tmpNums[i] = nums[cur2];tmpIndex[i++] = index[cur2++];//下标数组同步修改}else{ret[index[cur1]] += right - cur2 + 1;//结果在原数组下标对应值位置上tmpNums[i] = nums[cur1];tmpIndex[i++] = index[cur1++];}}while(cur1 <= mid) {tmpNums[i] = nums[cur1];tmpIndex[i++] = index[cur1++];}while(cur2 <= right){tmpNums[i] = nums[cur2];tmpIndex[i++] = index[cur2++];} for(int j = left; j <= right; j++){nums[j] = tmpNums[j - left];index[j] = tmpIndex[j - left];}}
}

493. 翻转对

解法

注意: 要先统计结果后,再进行排序

边界情况, 可以将2倍的数转为long,也可以使用 / 2.0 

代码

 策略一: 降序,谁大谁在前面

class Solution {int[] tmp; public int reversePairs(int[] nums) {int n = nums.length;tmp = new int[n];return merge(nums, 0, n - 1);}public int merge(int[] nums, int left, int right){if(left >= right) return 0;int mid = (left + right) / 2, ret = 0;ret += merge(nums, left, mid);ret += merge(nums, mid + 1, right);//[left, mid] [mid + 1, right]//先统计,后归并int x = left, y = mid + 1;while(x <= mid && y <= right){//降序if(nums[x] / 2.0 > nums[y] ){ret += right - y + 1;x++;}else{                y++;}}int cur1 = left, cur2 = mid + 1, i = 0;while(cur1 <= mid && cur2 <= right){if(nums[cur1] <= nums[cur2]){tmp[i++] = nums[cur2++];}else{                tmp[i++] = nums[cur1++];}}while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= right) tmp[i++] = nums[cur2++];for(int j = left; j <= right; j++){nums[j] = tmp[j - left];}return ret;}
}

策略二: 升序

class Solution {int[] tmp; public int reversePairs(int[] nums) {int n = nums.length;tmp = new int[n];return merge(nums, 0, n - 1);}public int merge(int[] nums, int left, int right){if(left >= right) return 0;int mid = (left + right) / 2, ret = 0;ret += merge(nums, left, mid);ret += merge(nums, mid + 1, right);//[left, mid] [mid + 1, right]//先统计,后归并int x = left, y = mid + 1;while(x <= mid && y <= right){//降序if(nums[x] / 2.0 > nums[y] ){ret += mid - x + 1;y++;}else{                x++;}}int cur1 = left, cur2 = mid + 1, i = 0;while(cur1 <= mid && cur2 <= right){if(nums[cur1] <= nums[cur2]){tmp[i++] = nums[cur1++];}else{                tmp[i++] = nums[cur2++];}}while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= right) tmp[i++] = nums[cur2++];for(int j = left; j <= right; j++){nums[j] = tmp[j - left];}return ret;}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/34580.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

docker入门篇

使用docker可以很快部署相同的环境,这也是最快的环境构建,接下来就主要对docker中的基础内容进行讲解.Docker 是一个用于开发、交付和运行应用程序的开源平台&#xff0c;它可以让开发者将应用程序及其依赖打包到一个容器中&#xff0c;然后在任何环境中运行这个容器&#xff0…

Learning vtkjs之ContourLoopExtraction

过滤器 等高线轮廓提取 介绍 这个过滤器可以获取一个cut的相交的循环的线&#xff0c;目前这个案例cut是一个平面&#xff0c;应该是可以支持更多隐式公式 效果 可以设置这个平面的原点Origin 法线方向Normal&#xff0c;然后就可以求交了 核心代码 需要实现这个代码主要…

如何高效解决 Java 内存泄漏问题方法论

目录 一、系统化的诊断与优化方法论 二、获取内存快照&#xff1a;内存泄漏的第一步 &#xff08;一&#xff09;自动生成 Heap Dump &#xff08;二&#xff09;手动生成 Heap Dump 三、导入分析工具&#xff1a;MAT 和 JProfiler &#xff08;一&#xff09;MAT (Memor…

新手村:数据预处理-异常值检测方法

机器学习中异常值检测方法 一、前置条件 知识领域要求编程基础Python基础&#xff08;变量、循环、函数&#xff09;、Jupyter Notebook或PyCharm使用。统计学基础理解均值、中位数、标准差、四分位数、正态分布、Z-score等概念。机器学习基础熟悉监督/无监督学习、分类、聚类…

大模型-提示词调优

什么是提示词 提示词&#xff08;Prompt&#xff09;在大模型应用中扮演着关键角色&#xff0c;它是用户输入给模型的一段文本指令 。简单来说&#xff0c;就是我们向大模型提出问题、请求或描述任务时所使用的文字内容。例如&#xff0c;当我们想让模型写一篇关于春天的散文&a…

VS2022输入 scanf 报错解决方法

1.第一种解决办法&#xff08;不推荐&#xff09; •将 scanf 替换为 scanf_s •scanf_s 是VS提供的一个函数&#xff0c;scanf_s函数的使用和scanf是有区别的 •scanf_s 是VS提供的一个函数&#xff0c;其他的编译器可能不认识这个函数&#xff0c;那么我们所写的代码就存在跨…

鸿蒙开发-一多开发之媒体查询功能

在HarmonyOS中&#xff0c;使用ArkTS语法实现响应式布局的媒体查询是一个强大的功能&#xff0c;它允许开发者根据不同的设备特征&#xff08;如屏幕尺寸、屏幕方向等&#xff09;动态地调整UI布局和样式。以下是一个使用媒体查询实现响应式布局的实例&#xff1a; 1. 导入必要…

火语言RPA--列表项内容获取

【组件功能】&#xff1a;获取列表中某项数据内容 配置预览 配置说明 获取 获取数据方式 首项&#xff1a;列表第一条数据 末项&#xff1a;列表最后一条数据 随机项&#xff1a;随机获取列表中一条数据 指定索引项&#xff1a;根据索引获取列表对象中数据。 索引项目位置 …

基于Python+Flask+MySQL+HTML的爬取豆瓣电影top-250数据并进行可视化的数据可视化平台

FlaskMySQLHTML 项目采用前后端分离技术&#xff0c;包含完整的前端&#xff0c;以flask作为后端 Pyecharts、jieba进行前端图表展示 通过MySQL收集格列数据 通过Pyecharts制作数据图表 这是博主b站发布的详细讲解&#xff0c;感兴趣的可以去观看&#xff1a;【Python爬虫可…

解锁MySQL 8.0.14源码调试:Mac 11.6+CLion 2024.3.4实战指南

文章目录 解锁MySQL 8.0.41源码调试&#xff1a;Mac 11.6CLion 2024.3.4实战指南前期准备环境搭建详细步骤安装 CLion安装 CMake 3.30.5准备 MySQL 8.0.14 源码配置 CMake 选项构建 MySQL 项目 调试环境配置与验证配置 LLDB 调试器启动调试验证调试环境 总结与拓展 解锁MySQL 8…

81.HarmonyOS NEXT 状态管理与响应式编程:@Observed深度解析

温馨提示&#xff1a;本篇博客的详细代码已发布到 git : https://gitcode.com/nutpi/HarmonyosNext 可以下载运行哦&#xff01; HarmonyOS NEXT 状态管理与响应式编程&#xff1a;Observed深度解析 文章目录 HarmonyOS NEXT 状态管理与响应式编程&#xff1a;Observed深度解析…

【快速入门】MyBatis

一.基础操作 1.准备工作 1&#xff09;引入依赖 一个是mysql驱动包&#xff0c;一个是mybatis的依赖包&#xff1a; <dependency><groupId>org.mybatis.spring.boot</groupId><artifactId>mybatis-spring-boot-starter</artifactId><vers…

RabbitMQ可靠性进制

文章目录 1.生产者可靠性生产者重连生产者确认小结 2. MQ的可靠性数据持久化LazyQueue小结 3. 消费者的可靠性消费者确认机制消费者失败处理方案业务幂等性唯一消息ID业务判断 兜底方案业务判断 兜底方案 1.生产者可靠性 生产者重连 在某些场景下由于网络波动&#xff0c;可能…

【专项测试】限流测试

简介 限流的目的是防止恶意请求、恶意攻击&#xff0c;或者防止流量超出系统峰值时保护系统免受灭顶之灾。 限流的具体做法是是通过对并发访问/请求进行限速或者对一个时间窗口的请求进行限速在保护系统&#xff0c;一旦达到限制速率则可以拒绝服务&#xff08;定向到错误页&a…

Qt-D指针与Q指针的设计哲学

文章目录 前言PIMLP与二进制兼容性D指针Q指针优化d指针继承Q_D和Q_Q 前言 在探索Qt源码的过程中会看到类的成员有一个d指针&#xff0c;d指针类型是一个private的类&#xff0c;这种设计模式称为PIMPL&#xff08;pointer to implementation&#xff09;&#xff0c;本文根据Q…

ctf web入门知识合集

文章目录 01做题思路02信息泄露及利用robots.txt.git文件泄露dirsearch ctfshow做题记录信息搜集web1web2web3web4web5web6web7web8SVN泄露与 Git泄露的区别web9web10 php的基础概念php的基础语法1. PHP 基本语法结构2. PHP 变量3.输出数据4.数组5.超全局变量6.文件操作 php的命…

LangChain 工作流编排

文章目录 LCEL流式调用案例invoke的异步调用异步流中的事件 LCEL LangChain Expression Language&#xff0c;是一种强大的工作流编排工具&#xff0c;可以从基本组件构建复杂的任务链&#xff08;Chain&#xff09;&#xff0c;有如下亮点&#xff1a; 流式支持&#xff1b;…

PyTorch 深度学习实战(14):Deep Deterministic Policy Gradient (DDPG) 算法

在上一篇文章中&#xff0c;我们介绍了 Proximal Policy Optimization (PPO) 算法&#xff0c;并使用它解决了 CartPole 问题。本文将深入探讨 Deep Deterministic Policy Gradient (DDPG) 算法&#xff0c;这是一种用于连续动作空间的强化学习算法。我们将使用 PyTorch 实现 D…

3.14-1列表

列表 一.列表的介绍和定义 1 .列表 类型: <class list> 2.符号:[] 3.定义列表: 方式1:[] 通过[] 来定义 list[1,2,3,4,6] print(type(list)) #<class list> 方式2: 通过list 转换 str2"12345" print(type(str2)) #<class str> list2lis…

Java集合 - HashMap

HashMap 是 Java 集合框架中的一个重要类&#xff0c;位于 java.util 包中。它实现了 Map 接口&#xff0c;基于哈希表的数据结构来存储键值对&#xff08;key-value pairs&#xff09;。HashMap 允许使用 null 作为键和值&#xff0c;并且是非同步的&#xff08;非线程安全的&…