当前位置: 首页 > news >正文

数据结构笔记--归并排序及其拓展题(小和问题、逆序对问题)

目录

1--归并排序

2--小和问题

3--逆序对问题


1--归并排序

        归并排序的核心思想:将一个无序的序列归并排序为一个有序的系列;通过递归将无序的序列二分,从底层开始将二分的序列归并排序为有序序列;

#include <iostream>
#include <vector>class Solution{
public:std::vector<int> Merge_Sort(std::vector<int> arr){if(arr.size() <= 1) return arr;split(arr, 0, arr.size() - 1);return arr;}// 二分void split(std::vector<int> &arr, int l, int r){if(l == r) return;int mid = l + (r - l) / 2;split(arr, l, mid);split(arr, mid+1, r);// 归并merge(arr, l, mid, mid+1, r);}void merge(std::vector<int> &arr, int l1, int r1, int l2, int r2){std::vector<int> res;int i = l1, j = l2;while(i <= r1 && j <= r2){if (arr[i] < arr[j]){res.push_back(arr[i]);i++;}else{res.push_back(arr[j]);j++;}}while(i <= r1){res.push_back(arr[i]);i++;}while(j <= r2){res.push_back(arr[j]);j++;}for(int i = 0, j = l1; j <= r2; i++, j++){arr[j] = res[i];}}
};int main(){std::vector<int> input = {1, 3, 4, 2, 5};Solution S1;std::vector<int> res = S1.Merge_Sort(input);for(int num : res) std::cout << num << " ";return 0;
}

2--小和问题

        在一个数组中,每一个数左边比当前数小的数累加起来,叫做这个数组的小和,请编码实现求解一个数组的小和;

        实例,给定数组 [1, 3, 4, 2, 5],1 左边比 1 小的数,没有;3 左边比 3 小的数, 为 1;4 左边比 4 小的数, 为 1 和 3;2 左边比 2 小的数,为 1;5 左边比 5 小的数,为 1, 3, 4 和 2;因此数组的小数和为:1 + (1+3) + (1) + (1+3+4+2) = 16;

主要思路:

        在归并排序两两比较两个数组的元素时,就确定对应的小数和;具体做法是,分析当前数是另一个数组中多少个数的小数,即当前数多少次被用于计算小数和;

#include <iostream>
#include <vector>class Solution{
public:int Merge_Sort(std::vector<int> arr){if(arr.size() <= 1) return 0;int sum = split(arr, 0, arr.size() - 1);return sum;}// 二分int split(std::vector<int> &arr, int l, int r){if(l == r) return 0;int mid = l + (r - l) / 2;int count1 = split(arr, l, mid);int count2 = split(arr, mid+1, r);int count3 = merge(arr, l, mid, mid+1, r);// 归并return count1 + count2 + count3;}int merge(std::vector<int> &arr, int l1, int r1, int l2, int r2){int sum = 0;std::vector<int> res;int i = l1, j = l2;while(i <= r1 && j <= r2){if (arr[i] < arr[j]){// 对于 arr[j, r2] 的数都会大于 arr[i],因此它们的小数和都包含arr[i]sum += (r2 - j + 1) * arr[i];res.push_back(arr[i]);i++;}else{res.push_back(arr[j]);j++;}}while(i <= r1){res.push_back(arr[i]);i++;}while(j <= r2){res.push_back(arr[j]);j++;}for(int i = 0, j = l1; j <= r2; i++, j++){arr[j] = res[i];}return sum;}
};int main(){std::vector<int> input = {1, 3, 4, 2, 5};Solution S1;int res = S1.Merge_Sort(input);std::cout << res << " " << std::endl;return 0;
}

3--逆序对问题

主要思路:

        在归并排序两两比较两个数组的元素时,就确定对应的逆序对;具体做法是,分析当前数(arr2)在另一个数组(arr1)中有多少个逆序数

#include <iostream>
#include <vector>class Solution{
public:int Merge_Sort(std::vector<int> arr){if(arr.size() <= 1) return 0;int sum = split(arr, 0, arr.size() - 1);return sum;}// 二分int split(std::vector<int> &arr, int l, int r){if(l == r) return 0;int mid = l + (r - l) / 2;int count1 = split(arr, l, mid);int count2 = split(arr, mid+1, r);int count3 = merge(arr, l, mid, mid+1, r);// 归并return count1 + count2 + count3;}int merge(std::vector<int> &arr, int l1, int r1, int l2, int r2){int sum = 0;std::vector<int> res;int i = l1, j = l2;while(i <= r1 && j <= r2){if (arr[i] > arr[j]){// 对于 arr[j, r2] 的数都会大于 arr[i],因此它们的小数和都包含arr[i]sum += (r1 - i + 1);res.push_back(arr[j]);j++;}else{res.push_back(arr[i]);i++;}}while(i <= r1){res.push_back(arr[i]);i++;}while(j <= r2){res.push_back(arr[j]);j++;}for(int i = 0, j = l1; j <= r2; i++, j++){arr[j] = res[i];}return sum;}
};int main(){std::vector<int> input = {7, 5, 6, 4};Solution S1;int res = S1.Merge_Sort(input);std::cout << res << " " << std::endl;return 0;
}

相关文章:

数据结构笔记--归并排序及其拓展题(小和问题、逆序对问题)

目录 1--归并排序 2--小和问题 3--逆序对问题 1--归并排序 归并排序的核心思想&#xff1a;将一个无序的序列归并排序为一个有序的系列&#xff1b;通过递归将无序的序列二分&#xff0c;从底层开始将二分的序列归并排序为有序序列&#xff1b; #include <iostream> #…...

flutter开发实战-实现css线性渐变转换flutter渐变LinearGradient功能

flutter开发实战-实现css线性渐变转换flutter渐变LinearGradient功能 在之前项目开发中&#xff0c;遇到更换样式&#xff0c;由于从服务器端获取的样式均为css属性值&#xff0c;需要将其转换成flutter类对应的属性值。这里只处理线性渐变linear-gradient 比如渐变 “linear-…...

python推理小游戏bagels

python推理小游戏bagels bagels是一个推理小游戏&#xff0c;你的朋友想到一个随机的、没有重复的3位数字&#xff0c;你尝试去猜测它是什么。每次猜测之后&#xff0c;朋友就会给出3中类型的线索&#xff1a; Bagels: 你猜测的3个数都不在神秘数字中&#xff1b;Pico&#x…...

DBSCAN聚类

一、概述 DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一种基于密度的聚类算法&#xff0c;簇集的划定完全由样本的聚集程度决定。聚集程度不足以构成簇落的那些样本视为噪声点&#xff0c;因此DBSCAN聚类的方式也可以用于异常点的检测。 二、算法…...

java+ssm美食推荐交流系统 7jsw7

随着社会的发展&#xff0c;美食推荐系统的管理形势越来越严峻。越来越多的用户利用互联网获得信息&#xff0c;但美食推荐信息鱼龙混杂&#xff0c;真假难以辨别。为了方便用户更好的获得美食推荐信息&#xff0c;因此&#xff0c;设计一款安全高效的美食推荐系统极为重要。 为…...

基于php雪花算法工具类Snowflake -来自chatGPT

<?phpclass Snowflake {// 定义Snowflake算法的各个参数private $workerIdBits 5;private $datacenterIdBits 5;private $sequenceBits 12;private $workerIdShift;private $datacenterIdShift;private $timestampLeftShift;private $maxWorkerId;private $maxDatacente…...

怎么加密文件夹才更安全?安全文件夹加密软件推荐

文件夹加密可以让其中数据更加安全&#xff0c;但并非所有加密方式都能够提高极高的安全强度。那么&#xff0c;怎么加密文件夹才更安全呢&#xff1f;下面我们就来了解一下那些安全的文件夹加密软件。 文件夹加密超级大师 如果要评选最安全的文件夹加密软件&#xff0c;那么文…...

知识分享和Tomcat简单部署press应用

一、简述静态网页和动态网页的区别。 静态网页: 静态网页是指运行于客户端的程序、网页、组件、纯粹HTML格式的网页; 如果有涉及网页内容的修改&#xff0c;就要修改源文件&#xff0c;重新上传到服务器。而且当网站信息量很大的时候&#xff0c;网页制作和维护都非常困…...

回归预测 | MATLAB实现SO-CNN-BiGRU蛇群算法优化卷积双向门控循环单元多输入单输出回归预测

回归预测 | MATLAB实现SO-CNN-BiGRU蛇群算法优化卷积双向门控循环单元多输入单输出回归预测 目录 回归预测 | MATLAB实现SO-CNN-BiGRU蛇群算法优化卷积双向门控循环单元多输入单输出回归预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 MATLAB实现SO-CNN-BiGRU蛇群算法…...

步入React前厅 - 组件和JSX

目录 扩展学习资料 购物车应用 编写React元素 /src/index.js 创建组件 /src/components/listItem.jsx /src/App.js 理解JSX【JavaScriptXML】 JSX是什么 JSX规则 /src/components/listItem.jsx 使用Fragments /src/App.js 为何要使用Fragments 表格中使用Fragme…...

SpringBoot整合Sfl4j+logback的实践

一、概述 对于一个web项目来说&#xff0c;日志框架是必不可少的&#xff0c;日志的记录可以帮助我们在开发以及维护过程中快速的定位错误。slf4j,log4j,logback,JDK Logging等这些日志框架都是我们常见的日志框架&#xff0c;本文主要介绍这些常见的日志框架关系和SpringBoot…...

IT 基础架构自动化

什么是 IT 基础架构自动化 IT 基础架构自动化是通过使用技术来控制和管理构成 IT 基础架构的软件、硬件、存储和其他网络组件来减少人为干预的过程&#xff0c;目标是构建高效、可靠的 IT 环境。 为什么要自动化 IT 基础架构 为客户和员工提供无缝的数字体验已成为企业的当务…...

Docker入门——保姆级

Docker概述 ​ —— Notes from WAX through KuangShen 准确来说&#xff0c;这是一篇学习笔记&#xff01;&#xff01;&#xff01; Docker为什么出现 一款产品&#xff1a;开发—上线 两套环境&#xff01;应用环境如何铜鼓&#xff1f; 开发 – 运维。避免“在我的电脑…...

MONGODB ---- Austindatabases 历年文章合集

开头还是介绍一下群&#xff0c;如果感兴趣polardb ,mongodb ,mysql ,postgresql ,redis 等有问题&#xff0c;有需求都可以加群群内有各大数据库行业大咖&#xff0c;CTO&#xff0c;可以解决你的问题。加群请联系 liuaustin3 &#xff0c;在新加的朋友会分到2群&#xff08;共…...

菠萝头 pinia和vuex对比 pinia比vuex更香 Pinia数据持久化及数据加密

前言 毕竟尤大佬都推荐使用pinia&#xff0c;支持vue2和vue3&#xff01; 如果熟悉vuex&#xff0c;花个把小时把pinia看一下&#xff0c;就不想用vuex了 支持选项式api和组合式api写法pinia没有mutations&#xff0c;只有&#xff1a;state、getters、actionspinia分模块不…...

机器学习笔记 - 关于GPT-4的一些问题清单

一、简述 据报道,GPT-4 的系统由八个模型组成,每个模型都有 2200 亿个参数。GPT-4 的参数总数估计约为 1.76 万亿个。 近年来,得益于 GPT-4 等高级语言模型的发展,自然语言处理(NLP) 取得了长足的进步。凭借其前所未有的规模和能力,GPT-4为语言 AI​​设立了新标准,并为机…...

sql 参数自动替换

需求&#xff1a;看日志时&#xff0c;有的sql 非常的长&#xff0c;参数比较多&#xff0c;无法直接在sql 客户端工具执行&#xff0c;如果一个一个的把问号占位符替换为参数太麻烦&#xff0c;因此写个html 小工具&#xff0c;批量替换&#xff1a; 代码&#xff1a; <!…...

Linux——设备树

目录 一、Linux 设备树的由来 二、Linux设备树的目的 1.平台识别 2.实时配置 3.设备植入 三、Linux 设备树的使用 1.基本数据格式 2.设备树实例解析 四、使用设备树的LED 驱动 五、习题 一、Linux 设备树的由来 在 Linux 内核源码的ARM 体系结构引入设备树之前&#x…...

网络:从socket编程的角度说明UDP和TCP的关系,http和tcp的区别

尝试从编程的角度解释各种网络协议。 UDP和TCP的关系 从Python的socket编程角度出发&#xff0c;UDP&#xff08;User Datagram Protocol&#xff09;和TCP&#xff08;Transmission Control Protocol&#xff09;是两种不同的传输协议。 TCP是一种面向连接的协议&#xff0c…...

大数据技术之Hadoop:HDFS集群安装篇(三)

目录 分布式文件系统HDFS安装篇 一、为什么海量数据需要分布式存储 二、 分布式的基础架构分析 三、 HDFS的基础架构 四 HDFS集群环境部署 4.1 下载安装包 4.2 集群规划 4.3 上传解压 4.4 配置HDFS集群 4.5 准备数据目录 4.6 分发hadoop到其他服务器 4.7 配置环境变…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

自然语言处理——Transformer

自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效&#xff0c;它能挖掘数据中的时序信息以及语义信息&#xff0c;但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN&#xff0c;但是…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)

安全领域各种资源&#xff0c;学习文档&#xff0c;以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具&#xff0c;欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...

4. TypeScript 类型推断与类型组合

一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式&#xff0c;自动确定它们的类型。 这一特性减少了显式类型注解的需要&#xff0c;在保持类型安全的同时简化了代码。通过分析上下文和初始值&#xff0c;TypeSc…...

python爬虫——气象数据爬取

一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用&#xff1a; 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests&#xff1a;发送 …...

LangFlow技术架构分析

&#x1f527; LangFlow 的可视化技术栈 前端节点编辑器 底层框架&#xff1a;基于 &#xff08;一个现代化的 React 节点绘图库&#xff09; 功能&#xff1a; 拖拽式构建 LangGraph 状态机 实时连线定义节点依赖关系 可视化调试循环和分支逻辑 与 LangGraph 的深…...

【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅!

【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅! 🌱 前言:一棵树的浪漫,从数组开始说起 程序员的世界里,数组是最常见的基本结构之一,几乎每种语言、每种算法都少不了它。可你有没有想过,一组看似“线性排列”的有序数组,竟然可以**“长”成一棵平衡的二…...

STM32标准库-ADC数模转换器

文章目录 一、ADC1.1简介1. 2逐次逼近型ADC1.3ADC框图1.4ADC基本结构1.4.1 信号 “上车点”&#xff1a;输入模块&#xff08;GPIO、温度、V_REFINT&#xff09;1.4.2 信号 “调度站”&#xff1a;多路开关1.4.3 信号 “加工厂”&#xff1a;ADC 转换器&#xff08;规则组 注入…...

用神经网络读懂你的“心情”:揭秘情绪识别系统背后的AI魔法

用神经网络读懂你的“心情”:揭秘情绪识别系统背后的AI魔法 大家好,我是Echo_Wish。最近刷短视频、看直播,有没有发现,越来越多的应用都开始“懂你”了——它们能感知你的情绪,推荐更合适的内容,甚至帮客服识别用户情绪,提升服务体验。这背后,神经网络在悄悄发力,撑起…...