算法分析—— 《归并排序》

《排序数组》

题目描述:

给你一个整数数组 nums,请你将该数组升序排列。

你必须在 不使用任何内置函数 的情况下解决问题,时间复杂度为 O(nlog(n)),并且空间复杂度尽可能小。

示例 1:

输入:nums = [5,2,3,1]
输出:[1,2,3,5]

示例 2:

输入:nums = [5,1,1,2,0,0]
输出:[0,0,1,1,2,5]

代码实现:

class Solution 
{
public:
    vector<int> tmp;
    vector<int> sortArray(vector<int>& nums) 
    {
        tmp.resize(nums.size());
        MergeSort(nums, 0, nums.size() - 1);
        return nums;
    }

    void MergeSort(vector<int>& nums, int l, int r)
    {
        if(l >= r) return;

        int mid = (r + l) >> 1;

        MergeSort(nums, l, mid);
        MergeSort(nums, mid + 1, r);

        int cur1 = l, cur2 = mid + 1, i = 0;
        while(cur1 <= mid && cur2 <= r) 
            tmp[i++] = nums[cur1] >= nums[cur2] ? nums[cur2++] : nums[cur1++];
        
        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= r) tmp[i++] = nums[cur2++];

        for(int i = l; i <= r; ++i) nums[i] = tmp[i - l];
    }
};

代码解析:

对于同一种排序题目来说,不仅仅要去掌握快速排序,接触其他的排序新思路也尤为重要,不管是归并排序还是快速排序,其本质的思路就是两个字 —— 分治。

所以归并排序是最简单的,利用递归的思路,我们就认为这个递归操作一定可以做到,那么最终就是实现一个「合并两个有序数组」的操作。

那这个操作很简单,利用双指针就可以非常轻松的实现了,在这里我就不过多赘述,因为确实不难。

《交易逆序对的总数》

题目描述:

在股票交易中,如果前一天的股价高于后一天的股价,则可以认为存在一个「交易逆序对」。请设计一个程序,输入一段时间内的股票交易记录 record,返回其中存在的「交易逆序对」总数。

示例 1:

输入:record = [9, 7, 5, 4, 6]
输出:8
解释:交易中的逆序对为 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。

代码实现:

class Solution 
{
public:
    vector<int> tmp;
    int reversePairs(vector<int>& record) 
    {
        tmp.resize(record.size());
        return mergesort(record, 0, record.size() - 1);
    }

    int mergesort(vector<int>& record, int left, int right)
    {
        if(left >= right) return 0;

        int mid = (left + right) >> 1;
        
        int ret = 0;

        ret += mergesort(record, left, mid);
        ret += mergesort(record, mid + 1, right);

        int cur1 = left, cur2 = mid + 1, i = 0;

        while(cur1 <= mid && cur2 <= right)
        {
            if(record[cur1] <= record[cur2]) tmp[i++] = record[cur1++];
            else 
            {
                ret += (mid - cur1 + 1);
                tmp[i++] = record[cur2++];
            } 
        }

        while(cur1 <= mid) tmp[i++] = record[cur1++];
        while(cur2 <= right) tmp[i++] = record[cur2++];

        for(int i = left; i <= right; ++i)
        {
            record[i] = tmp[i - left];
        }
        return ret;
    }

};

代码解析:

题目意思很好理解,就是定一个数字,然后去后面找有没有比这个数小的,记住一定是要去后面找。

最简单的解法就是利用双指针套两层for循环直接暴力解决,但是最终会超时,这就很尴尬。

第二个方法,就是利用分治归并的思路来解决题目。

我们最主要的研究可以转换成「找出该数前,有多少个数比我大」

那现在假设我们利用了「归并」将数组排好了升序了,但是还没有「合并两个有序数组」,大致的情况如下:

因为这个判断也需要指针移动,所以我们就可以在排序的过程中,就将答案给算出来。

因为单调性,所以在nums[cur1] > nums[cur2]的情况下,cur1后面的数都大于nums[cur2]

《计算右侧小于当前元素的个数》

题目描述:

给你一个整数数组 nums ,按要求返回一个新数组 counts 。数组 counts 有该性质: counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

示例 1:

输入:nums = [5,2,6,1]
输出:[2,1,1,0] 
解释:
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素

示例 2:

输入:nums = [-1]
输出:[0]

示例 3:

输入:nums = [-1,-1]
输出:[0,0]

代码实现:

class Solution 
{
public:
    vector<pair<int, int>> tmp;     // 追踪nums
    vector<int> ret;                // 接受答案
    vector<pair<int, int>> assist;  // 哈希绑定(原数据 + 下标)

    vector<int> countSmaller(vector<int> &nums)
    {
        for (int i = 0; i < nums.size(); ++i)
        {
            assist.push_back(make_pair(nums[i], i));
        }
        ret.resize(nums.size());
        tmp.resize(assist.size());

        Mergesort(assist, 0, nums.size() - 1);
        return ret;
    }

    void Mergesort(vector<pair<int, int>> &assist, int left, int right)
    {
        if (left >= right) return;

        int mid = (right + left) >> 1;

        Mergesort(assist, left, mid);
        Mergesort(assist, mid + 1, right);

        int cur1 = left, cur2 = mid + 1, i = 0;
        while (cur1 <= mid && cur2 <= right)
        {
            if (assist[cur1].first <= assist[cur2].first) tmp[i++] = assist[cur2++];
            else
            {
                ret[assist[cur1].second] += right - cur2 + 1;
                tmp[i++] = assist[cur1++];
            }
        }

        while (cur1 <= mid) tmp[i++] = assist[cur1++];
        while (cur2 <= right) tmp[i++] = assist[cur2++];

        for (int i = left; i <= right; ++i) assist[i] = tmp[i - left];
    }

};

代码解析:

这道题目总体来说,与上一道题的算法思路一样,上一道题是记录有多少个前面大于后面的数字,而这道题是将每个坐标的数字统计起来,然后将确切的数据按照下标统计。

所以使用归并排序,我们无法固定住下标,因为下标会随着排序而发生变化。所以这正是我们需要去解决的。

一开始我考虑使用哈希表,但是数组可能会出现重复数据,所以哈希表pass了,但是我们可以仍然采用哈希的算法思路,将数据和下标绑定在一起。那么这时候我们可以使用vector<pair<int, int>>来模拟哈希表。

拿题目自带的例子:

这样子在排序改变数据位置的同时,下标也随之改变了。

然后也是基于上一道题了,不过这里我们不应该排「升序」,而是排「降序」,因为我们是要找右侧有多少个元素比自己小,那竟然如此我们可以画个图理解理解。

因为单调性,所以nums[cur1]大于cur2后面的全部数。

剩下的思路也是一样的,只是需要注意pair的first和seconde的取值。

《翻转对》

题目描述:

给定一个数组 nums ,如果 i < jnums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对****。

你需要返回给定数组中的重要翻转对的数量。

示例 1:

输入: [1,3,2,3,1]
输出: 2

示例 2:

输入: [2,4,3,5,1]
输出: 3

注意:

  1. 给定数组的长度不会超过50000
  2. 输入数组中的所有数字都在32位整数的表示范围内。

代码实现:

class Solution 
{
public:
    vector<int> tmp;
    int reversePairs(vector<int>& nums) 
    {
        tmp.resize(nums.size());
        return MergeSort(nums, 0, nums.size() - 1);
    }

    int MergeSort(vector<int>& nums, int left, int right)
    {
        if(left >= right) return 0;

        int mid = (left + right) >> 1;

        int ret = 0;

        ret += MergeSort(nums, left, mid);
        ret += MergeSort(nums, mid + 1, right);

        int cur1 = left, cur2 = mid + 1, i = 0;

        while(cur1 <= mid)
        {
            while(cur2 <= right && nums[cur1] / 2.0 <= nums[cur2]) ++cur2;
            if(cur2 > right) break;

            ret += (right - cur2 + 1);
            ++cur1;
        }

        cur1 = left, cur2 = mid + 1;
        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++];

        for(int i = left; i <= right; ++i) nums[i] = tmp[i - left];

        return ret;
    }

};

代码解析:

一样,这道题和前面的内容算法一样,只不过这里是判断是否大于2倍。

那在这里我们在实现「合并两个有序数组」之前,就可以先通过双指针进行一次判断,再去排序,因为你无法控制是以2倍为标准然后向右移动还是统计数据,而且经过排序后,数据也会乱了,因此我们必须在排序之前就通过双指针做好统计。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

linux云服务器部署deepseek,并通过网页访问

参考视频&#xff1a;https://www.douyin.com/root/search/linux%E5%AE%89%E8%A3%85%20deepseek?aid3aa2527c-e4f2-4059-b724-ab81a140fa8b&modal_id7468518885570940214&typegeneral 修改ollama配置文件 vim /etc/systemd/system/ollama.service 我的电脑硬盘只有4…

FastAdmin后端列表导入表格数据

后台添加数据的时候增加通过表格导入功能 如下图index.html页面增加导入和模板下载按钮代码如下 <div class"panel panel-default panel-intro">{:build_heading()}<div class"panel-body"><div id"myTabContent" class"ta…

可调节图片参数,解决图片模糊及尺寸过小问题的工具

软件介绍 你是否正为图片模糊、尺寸太小而烦恼&#xff1f;别担心&#xff0c;有这样一款神器能帮你轻松解决。它能精准调节图片参数&#xff0c;即便原本模糊不清的图片&#xff0c;经它处理后也能变得高清锐利&#xff0c;瞬间让图片焕然一新。而且&#xff0c;它还具备导出…

Windows网络安全基础

随着互联网的发展和普及&#xff0c;Windows网络安全问题愈发严重。在本文中&#xff0c;我们将会介绍Windows网络安全的基本概念&#xff0c;包括网络攻击类型、网络安全威胁、网络安全防御措施等等&#xff0c;帮助初学者更好地了解Windows网络安全。 一、网络攻击类型 网络…

代码补全『三重奏』:EverEdit如何用上下文识别+语法感知+智能片段重构你的编码效率!

1 代码自动完成 1.1 应用场景 在编辑文档时&#xff0c;为了提高编辑效率&#xff0c;编辑器一般都会带有自动完成功能&#xff0c;比如&#xff1a;输入括号时自动补全另一半&#xff0c;输入文字时&#xff0c;自动补全剩下的部分。 1.2 使用方法 1.2.1 自动缩进 单击主菜…

vue,vue3 keepalive没有效果,无法缓存页面include无效,keep-alive

keepalive没有效果&#xff0c;无法缓存页面&#xff1f; 问题大概是组件的name值不对应&#xff0c;vue2修改组件文件的name值&#xff0c;vue3保持组件文件名称和路由页面配置的name一致就可以了&#xff0c;如果vue3不想保持一致&#xff0c;必须手动在文件后面添加export..…

栈回溯方案

注&#xff1a;栈回溯无法很好的定位到未调优化的函数&#xff0c;需要编译前使用 -fno-optimize-sibling-calls 选项禁止尾调优化。 基于unwind的栈回溯 在 arm 架构下&#xff0c;不少32位系统用的是 unwind 形式的栈回溯&#xff0c;这种栈回溯要复杂很多。首先需要程序有一…

【存储中间件API】MySQL、Redis、MongoDB、ES常见api操作及性能比较

常见中间件api操作及性能比较 ☝️ MySQL crud操作✌️ maven依赖✌️ 配置✌️ 定义实体类✌️ 常用api ☝️ Redis crud操作✌️ maven依赖✌️ 配置✌️ 常用api ☝️ MongoDB crud操作✌️ maven依赖✌️ 配置文件✌️ 定义实体类✌️ MongoDB常用api ☝️ ES crud操作 ⭐️…

解锁D3.js与PlantUML的交互奥秘:探索知识图谱数据可视化新领域

解锁D3.js与PlantUML的交互魔法&#xff1a;数据可视化新征程 在前端开发的广袤天地里&#xff0c;数据可视化一直是一颗璀璨的明珠&#xff0c;吸引着无数开发者探索其奥秘。而当D3.js这一强大的JavaScript库&#xff0c;遇上专注于创建UML图的PlantUML&#xff0c;一场奇妙的…

DeepSeek24小时写作机器人,持续创作高质量文案

内容创作已成为企业、自媒体和创作者的核心竞争力。面对海量的内容需求&#xff0c;人工创作效率低、成本高、质量参差不齐等问题日益凸显。如何在有限时间内产出高质量内容&#xff1f;DeepSeek写作机器人&#xff0c;一款24小时持续创作的智能工具&#xff0c;为企业和个人提…

使用html css js 来实现一个服装行业的企业站源码-静态网站模板

最近在练习 前端基础&#xff0c;html css 和js 为了加强 代码的 熟悉程序&#xff0c;就使用 前端 写了一个个服装行业的企业站。把使用的技术 和 页面效果分享给大家。 应用场景 该制衣服装工厂官网前端静态网站模板主要用于前端练习和编程练习&#xff0c;适合初学者进行 HT…

使用html css js 开发一个 教育机构前端静态网站模板

这个教育机构网站模板是专为前端开发初学者设计的练习项目&#xff0c;适合正在学习前端的学生或自学者使用。网站内容包括首页、课程体系、师资力量、关于我们和联系我们等基础页面&#xff0c;帮助学习者熟悉网页布局、样式设计和交互功能的实现。 静态页面 简单截图 应用…

(蓝桥杯——10. 小郑做志愿者)洛斯里克城志愿者问题详解

题目背景 小郑是一名大学生,她决定通过做志愿者来增加自己的综合分。她的任务是帮助游客解决交通困难的问题。洛斯里克城是一个六朝古都,拥有 N 个区域和古老的地铁系统。地铁线路覆盖了树形结构上的某些路径,游客会询问两个区域是否可以通过某条地铁线路直达,以及有多少条…

React 低代码项目:网络请求与问卷基础实现

&#x1f35e;吐司问卷&#xff1a;网络请求与问卷基础实现 Date: February 10, 2025 Log 技术要点&#xff1a; HTTP协议XMLHttpRequest、fetch、axiosmock.js、postmanWebpack devServer 代理、craco.js 扩展 webpackRestful API 开发要点&#xff1a; 搭建 mock 服务 …

大流量汽(柴)油机泵,抗洪抢险的可靠选择|深圳鼎跃

近年来&#xff0c;全球范围内极端天气频发&#xff0c;洪涝灾害成为危及人民生命财产安全的重要因素。在抗洪抢险行动中&#xff0c;如何迅速、高效地排除积水&#xff0c;保障救援通道和安全区域成为关键。汽柴油机泵凭借其动力强、移动灵活、环境适应性强等特点&#xff0c;…

游戏开发微信小程序--工具箱之父

小程序工具箱之父已更新 Page({data: {score: 0,lives: 3,gameOver: false,playerVisible: true,level: 1,petType: cat,speedBuff: 1,coins: 0,friends: [],achievements: [],currentPetFrame: 0, // 当前宠物动画帧scoreMultiplier: 1, // 得分倍率gameSpeed: 1, // …

一.数据治理理论架构

1、数据治理核心思想&#xff1a; 数据治理理论架构图描绘了一个由顶层设计、管控机制、核心领域和管理系统四个主要部分组成的数据治理框架。它旨在通过系统化的方法&#xff0c;解决数据治理机制缺失引发的业务和技术问题&#xff0c;并最终提升企业的数据管理水平。 数据治…

一键安装教程

有需要的可以私信 亮点&#xff1a; 不再需要安装完去配置环境变量&#xff0c;下载完程序&#xff0c;解压后&#xff0c;右键进行管理员安装&#xff0c;安装完毕自动配置环境变量&#xff0c;即可使用 Maven 安装 右键 以管理员身份运行点击 下一步安装完成后会同步配置环境…

crud项目分析(2)

JWT令牌验证是否登录成功 简单的验证账号密码是否正确(存在) 全局异常处理器 过滤器 因为login下只有这一个网页 唯一一种操作 package com.itheima.filter;import ch.qos.logback.core.util.StringUtil; import com.alibaba.fastjson.JSONObject; import com.itheima.pojo.R…

深入解析iOS视频录制(二):自定义UI的实现

深入解析 iOS 视频录制&#xff08;一&#xff09;&#xff1a;录制管理核心MWRecordingController 类的设计与实现 深入解析iOS视频录制&#xff08;二&#xff09;&#xff1a;自定义UI的实现​​​​​​​ 深入解析 iOS 视频录制&#xff08;三&#xff09;&#xff1a;完…