【算法总结】归并排序专题(刷题有感)

思考

一定要注意归并排序的含义，思考归并的意义。
主要分为两个步骤：

  1. 拆分
    1. 每次对半分(mid = l +r >> 1)
    2. 输入：raw整块，输出：raw左块+ raw右块
  2. 合并
    1. 每次都要对raw左块、 raw右块按照某种规则进行合并
    2. 输入：raw左块+ raw右块，输出：raw整块

知道两个步骤之后，可以总结其他的特点：

  1. 拆分阶段和合并阶段是一一对应的，只不过拆分阶段是raw的，合并阶段符合一定的性质(对于归并排序则满足有序性)。
  2. 拆分时，段内是无序的，合并时，每一段都是有序的(数值有序性)。合并是针对两个有序的段进行合并，所以会经常用到双指针算法。
  3. 如下图所示，在合并过程中，段内是数值有序，但是相对顺序被破坏了，而两个段之间的相对顺序是不变的。6、7、8相对于1、2、3的顺序是不变的，6、7、8依然在1、2、3的左边。

几道题做下来，感觉归并排序类型题的难点在于

  1. 题意的转化：重点就要题意是否支持将原模型分成两半来考虑，即计算左段相对后段的某种性质。
  2. 合并阶段对结果的计算，比如说求逆序对，那么合并的时候如何求逆序对的个数，双重循环遍历？双指针？等等。。。

普通模板

int* merge(int l, int r) {
    if (l > r) return nullptr;
    
    int* tmp = new int[r - l + 1];
    
    if (l == r) {
        tmp[0] = a[l];
        return tmp;
    }
    
    int mid = l + ((r - l) >> 1);
    
    int llen = mid - l + 1, rlen = r - mid;
    int* la = merge(l, mid);
    int* ra = merge(mid + 1, r);
    
    int i = 0, j = 0, cnt = 0;
    for (; i < llen && j < rlen; ) {
        if (la[i] > ra[j]) {
            tmp[cnt ++] = ra[j ++];
        } else {
            tmp[cnt ++] = la[i ++];
        }
    }
    // 上边的循环结束之后，可能存在一个数组还未完全遍历。
    while(i < llen) tmp[cnt ++] = la[i ++];
    while(j < rlen) tmp[cnt ++] = ra[j ++];
    return tmp;
}

Acwing 787. 归并排序

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>

using namespace std;


const int N = 100000 + 100;
int a[N], tmp[N];

void merge(int q[], int l, int r) {
    if (l >= r) return;
    
    int mid = l + ((r - l) >> 1);

    merge(q, l, mid);
    merge(q, mid + 1, r);
    
    int i = l, j = mid + 1, cnt = 0;
    for (; i <= mid && j <= r; ) {
        if (q[i] > q[j]) {
            tmp[cnt ++] = q[j ++];
        } else {
            tmp[cnt ++] = q[i ++];
        }
    }
    while(i <= mid) tmp[cnt ++] = q[i ++];
    while(j <= r) tmp[cnt ++] = q[j ++];
    
    for (int i = l, j = 0; i <= r; i ++, j ++)
        q[i] = tmp[j];
}

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i ++) cin >> a[i];
    merge(a, 0, n - 1);
    
    for (int i = 0; i < n; i ++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

Acwing 788. 逆序对的数量

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long LL;

const int N = 100100;

int a[N];
int n;
LL ans;

void print_arr(int* arr, int size) {
    for (int i = 0; i < size; i ++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int* merge(int l, int r) {
    if (l > r) return nullptr;
    
    int* tmp = new int[r - l + 1];
    if (r == l) {
        tmp[0] = a[l];
        return tmp;
    }
    int mid = l + r >> 1;
    
    int* larr = merge(l, mid);
    int* rarr = merge(mid + 1, r);
    
    
    int llen = (mid - l) + 1, rlen = (r - mid - 1) + 1;
    // printf("l:\n");
    // print_arr(larr, llen);
    // printf("r:\n");
    // print_arr(rarr, rlen);
    
    int i = 0, j = 0, cnt = 0;
    for (; i < llen && j < rlen;)
    {
        if (larr[i] > rarr[j]) {
            
            ans += (llen - 1 - i) + 1;
            tmp[cnt ++] = rarr[j ++];
        } else {
            tmp[cnt ++] = larr[i ++];
        }
    }
    while(i < llen) tmp[cnt ++] = larr[i ++];
    while(j < rlen) tmp[cnt ++] = rarr[j ++];
    
    // printf("merge\n");
    // print_arr(tmp, (r - l) + 1);
    // printf("ans : %d\n", ans);
    return tmp;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++) cin >> a[i];
    int* h = merge(0, n - 1);
    // for (int i = 0; i < n; i ++) {
    //     printf("%d\n", h[i]);
    // }
    printf("%lld\n", ans);
    return 0;
}

Leetcode 493. 翻转对

class Solution {
    long ans = 0;
    public int reversePairs(int[] nums) {
        int n = nums.length;
        mergeSort(nums, 0, n - 1);
        return (int)ans;
    }

    void mergeSort(int[] nums, int l, int r) {
        if (l >= r) return;
        int[] tmp = new int[r - l + 1];

        int mid = l + ((r - l) >> 1);
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);

        int i = l, j = mid + 1, cnt = 0;
        int base = 0;
        for (; i <= mid; i ++) {
            while (j <= r && (long)nums[i] > 2L * nums[j]) {
                j ++;
            }
            ans += (j - (mid + 1));
        }
        i = l;
        j = mid + 1;
        for (; i <= mid && j <= r; ) {
            if (nums[i] > nums[j]) tmp[cnt ++] = nums[j ++];
            else tmp[cnt ++] = nums[i ++];
        }
        while(i <= mid) tmp[cnt ++] = nums[i ++];
        while(j <= r) tmp[cnt ++] = nums[j ++];
        for (int k = 0; k < cnt; k ++)
            nums[l + k] = tmp[k];
    }
}

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

  1. 这个题比较恶心的就是要维护元素原来的位置
class Node {
    int x;
    int id;
    Node(int x, int id) {
        this.x = x;
        this.id = id;
    }
}

class Solution {
    List<Integer> ans = null;
    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        ans = new ArrayList<>(Collections.nCopies(n, 0));
        Node[] nodes = new Node[n];
        for (int i = 0; i < n; i ++) {
            nodes[i] = new Node(nums[i], i);
        }
        merge(nodes, 0, n - 1);
        return ans;
    }

    void merge(Node[] nodes, int l, int r) {
        if (l >= r) return;

        Node[] tmp = new Node[r - l + 1];
        int mid = l + ((r - l) >> 1);
        merge(nodes, l, mid);
        merge(nodes, mid + 1, r);

        int i = l, j = mid + 1, cnt = 0;
        int base = 0;
        for (; i <= mid;) {
            if (j == r + 1 || nodes[i].x <= nodes[j].x) {
                ans.set(nodes[i].id, ans.get(nodes[i].id) + base);
                tmp[cnt ++] = nodes[i ++];
            } else {
                tmp[cnt ++] = nodes[j ++];
                base ++;
            }
        }
        while (j <= r) tmp[cnt ++] = nodes[j ++];

        for (int k = 0; k < cnt; k ++)
            nodes[l + k] = tmp[k];
    }
}

Leetcode 327. 区间和的个数(前缀和)

  1. 这个题首先要想到利用前缀和将原来的数组进行转换。
  2. 要求的是区间和属于[lower, upper]区间的个数，转化为数学符号之后就是这样： l o w e r < = s u m [ i ] − s u m [ j ] < = u p p e r lower <= sum[i] - sum[j] <= upper lower<=sum[i]−sum[j]<=upper
    1. 对于这样的不等式，可以分两步来考虑：
      1. 将连续不等式拆分成单个不等式， s u m [ i ] − s u m [ j ] < = u p p e r sum[i] - sum[j] <= upper sum[i]−sum[j]<=upper
      2. 将变量i固定，求另外一个变量的值
    2. 之后对于刚才的连续不等式就可以计算出符合条件的区间[m, n]
  3. 计算符合条件的区间的时机：在合并阶段，i的范围是[mid + 1, r]
class Solution {
    int lower = 0, upper = 0, ans = 0;
    public int countRangeSum(int[] nums, int lower, int upper) {
        this.upper = upper;
        this.lower = lower;
        int n = nums.length;

        long[] pre = new long[n + 1];
        for (int i = 1; i <= n; i ++)
            pre[i] = pre[i - 1] + nums[i - 1];
        merge(pre, 0, n);
        return ans;
    }

    void merge(long[] nums, int l, int r) {
        if (l >= r) return;

        long[] tmp = new long[r - l + 1];

        int mid = l + ((r - l) >> 1);
        merge(nums, l, mid);
        merge(nums, mid + 1, r);
    	// 核心代码
        for (int i = mid + 1, j = l, k = l; i <= r; i ++) {
            while (j <= mid && nums[i] - nums[j] > upper) j ++;
            while (k <= mid && nums[i] - nums[k] >= lower) k ++;
            ans += k - j;
        }
        
        int cnt = 0;
        for (int i = l, j = mid + 1; i <= mid || j <= r; ) {
            if (i == mid + 1) tmp[cnt ++] = nums[j ++];
            else if (j == r + 1) tmp[cnt ++] = nums[i ++];
            else {
                if (nums[i] > nums[j])
                    tmp[cnt ++] = nums[j ++];
                else
                    tmp[cnt ++] = nums[i ++];
            }
        }
        
        for (int i = 0; i < cnt; i ++)
            nums[i + l] = tmp[i];
    }
}

Acwing 65. 数组中的逆序对

  1. 题意就在题面上，所以直接套模板。
class Solution {
    int ans = 0;
    public int inversePairs(int[] nums) {
        int n = nums.length;
        mergeSort(nums, 0, n - 1);
        return ans;
    }
    
    void mergeSort(int[] nums, int l, int r) {
        if (l >= r) return;
        
        int[] tmp = new int[r - l + 1];
        int mid = l + ((r - l) >> 1);
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);
        
        int i = l, j = mid + 1, cnt = 0;
        for (; i <= mid && j <= r; ) {
            if (nums[i] > nums[j]) {
                ans += (mid - i) + 1;
                tmp[cnt ++] = nums[j ++];
            } else {
                tmp[cnt ++] = nums[i ++];
            }
        }
        while (i <= mid) tmp[cnt ++] = nums[i ++];
        while (j <= r) tmp[cnt ++] = nums[j ++];
        
        for (int k = 0; k < cnt; k ++)
            nums[l + k] = tmp[k];
    }
    
}

Acwing 107. 超快速排序

  1. 根据题意可以分析出本题是要求逆序的数量， 那就直接套模板。
import java.util.Scanner;

class Main {
    static long ans = 0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = 0;
        while((n = sc.nextInt()) != 0) {
            ans = 0;
            int[] nums = new int[n];    
            for (int i = 0; i < n; i ++) {
                nums[i] = sc.nextInt();
            }
            mergeSort(nums, 0, n - 1);
            System.out.println(ans);
        }
    }
    
    static void mergeSort(int[] nums, int l, int r) {
        if (l >= r) return;
        
        int[] tmp = new int[r - l + 1];
        int mid = l + ((r - l) >> 1);
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);
        
        int i = l, j = mid + 1, cnt = 0;
        for (; i <= mid && j <= r; ) {
            if (nums[i] > nums[j]) {
                ans += (mid - i) + 1;
                tmp[cnt ++] = nums[j ++];
            } else {
                tmp[cnt ++] = nums[i ++];
            }
        }
        while (i <= mid) tmp[cnt ++] = nums[i ++];
        while (j <= r) tmp[cnt ++] = nums[j ++];
        
        for (int k = 0; k < cnt; k ++)
            nums[l + k] = tmp[k];
    }
    
}

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

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

相关文章

2023.11.15-hivesql之炸裂函数explode练习

2023.11.15-hivesql之炸裂函数explode练习

把一个容器的多个数据炸裂出单独展示: explode(容器) 需求:将NBA总冠军球队数据使用explode进行拆分&#xff0c;并且根据夺冠年份进行倒序排序。 1.建表 --step1:建表 create table the_nba_championship(team_name string,champion_year array<string> ) row format…
阅读更多...
Minio安装

Minio安装

环境 centos8&#xff0c;关闭防火墙 minio-20231101183725版本 参考官网&#xff1a;部署 MinIO&#xff1a;单节点单硬盘 — 适用于 Linux 的 MinIO 对象存储 单例 下载rpm&#xff0c;用中国镜像 wget https://dl.minio.org.cn/server/minio/release/linux-amd64/arch…
阅读更多...
C语言判断水仙花数（ZZULIOJ1027:判断水仙花数）

C语言判断水仙花数（ZZULIOJ1027:判断水仙花数）

题目描述 春天是鲜花的季节&#xff0c;水仙花就是其中最迷人的代表&#xff0c;数学上有个水仙花数&#xff0c;他是这样定义的&#xff1a;“水仙花数”是指一个三位数&#xff0c;它的各位数字的立方和等于其本身&#xff0c;比如153135333。 现在要求输入一个三位数&#…
阅读更多...
数据分析 - 分散性与变异的量度

数据分析 - 分散性与变异的量度

全距 - 极差 处理变异性 方差度量 数值与均值的距离&#xff0c;也就是数据的差异性 标准差描述&#xff1a;典型值 和 均值的距离的方法&#xff0c;数据与均值的分散情况
阅读更多...
windows 安装 Oracle Database 19c

windows 安装 Oracle Database 19c

目录 什么是 Oracle 数据库 下载 Oracle 数据库 解压文件 运行安装程序 测试连接 什么是 Oracle 数据库 Oracle数据库是由美国Oracle Corporation&#xff08;甲骨文公司&#xff09;开发和提供的一种关系型数据库管理系统&#xff0c;它是一种强大的关系型数据库管理系统…
阅读更多...
用这个平台制作电子杂志,，还能实时分享，太方便啦！

用这个平台制作电子杂志,，还能实时分享，太方便啦！

在我们看电子杂志的时候&#xff0c;总会觉得图文效果有点枯燥&#xff0c;如果能做出翻页书效果的电子杂志&#xff0c;还给人一种身临其境的真实翻书感就好了。 其实制作这种翻页电子杂志很简单&#xff0c;不需要下载安装任何软件&#xff0c;只需登录FLBOOK这个平台 &…
阅读更多...
OCR文字识别标注小助手

OCR文字识别标注小助手

目录 背景 工具界面 操作 1、选择目录 2、更改为正确的信息 3、保存 4、说明 项目 代码 下载 背景 为什么要写这么一个小工具呢&#xff1f;因为要对文字进行标注。 为什么对文字进行标注呢&#xff1f;因为要重新训练识别。 为什么要重新训练识别呢&#xff1f;因…
阅读更多...
Linux 小程序－进度条

Linux 小程序－进度条

1.进度条准备知识 1.1回车与换行 以前的键盘会有一个这样的按键 &#xff0c;这个键就是回车与换行。 回车&#xff1a;从当前行回退到当前行的起始位置。 换行&#xff1a;从当前行切换到下一行的该位置。 有了以上的认识我们可以写出一个简单的倒计时代码&#xff1a; 注意&a…
阅读更多...
【华为HCIP | 华为数通工程师】IPV4与IPV6 高频题（2）

【华为HCIP | 华为数通工程师】IPV4与IPV6 高频题（2）

个人名片&#xff1a; &#x1f43c;作者简介&#xff1a;一名大三在校生&#xff0c;喜欢AI编程&#x1f38b; &#x1f43b;‍❄️个人主页&#x1f947;&#xff1a;落798. &#x1f43c;个人WeChat&#xff1a;hmmwx53 &#x1f54a;️系列专栏&#xff1a;&#x1f5bc;️…
阅读更多...
机器学习的线性回归与非线性回归

机器学习的线性回归与非线性回归

一元线性回归 回归分析用来建立方程模拟两个或者多个变量之间如何关联 一元线性回归包括一个自变量和一个因变量 如果包含两个以上的自变量&#xff0c;则称为多元线性回归 代价函数&#xff08;损失函数&#xff09; 损失函数的最终目的是为了使得误差平方和最小 用梯度下…
阅读更多...
【装包拆包----泛型】

【装包拆包----泛型】

文章目录 装箱和拆箱泛型创建一个泛型数组泛型的上界泛型方法 装箱和拆箱 装箱&#xff1a; 把基本数据类型给到引用数据类型 public static void main(String[] args) {//自动装包//第一种装包Integer c 12;//第二种装包int a 7;Integer b a;//显示装包Integer aa Intege…
阅读更多...
大语言模型|人工智能领域中备受关注的技术

大语言模型|人工智能领域中备受关注的技术

个人主页&#xff1a;【&#x1f60a;个人主页】 系列专栏&#xff1a;【❤️其他领域】 文章目录 前言关于大语言模型大语言模型是什么&#xff1f;大语言模型有什么用?文案写作知识库回答文本分类代码生成 AWS 如何通过 LLM 提供帮助&#xff1f;Amazon BedrockAmazon SageM…
阅读更多...
QT day3作业

QT day3作业

1.思维导图 2、 完善对话框&#xff0c;点击登录对话框&#xff0c;如果账号和密码匹配&#xff0c;则弹出信息对话框&#xff0c;给出提示”登录成功“&#xff0c;提供一个Ok按钮&#xff0c;用户点击Ok后&#xff0c;关闭登录界面&#xff0c;跳转到其他界面 如果账号和密…
阅读更多...
【Oracle 客户端连接数据库过程解析】

【Oracle 客户端连接数据库过程解析】

文章目录 一、开篇二、Oracle客户端简介三、连接过程解析 一、开篇 Oracle数据库以其卓越的性能和稳定性赢得了众多企业的信赖。作为开发者或数据库管理员&#xff0c;理解Oracle客户端如何与数据库建立连接&#xff0c;是确保系统正常运行的关键。 二、Oracle客户端简介 首…
阅读更多...
LabVIEW进行MQTT通信及数据解析

LabVIEW进行MQTT通信及数据解析

需求&#xff1a;一般通过串口的方式进行数据的解析&#xff0c;但有时候硬件的限制&#xff0c;没法预留串口&#xff0c;那么如何通过网络的方式特别是MQTT数据的通信及解析 解决方式&#xff1a; 1.MQTT通信控件&#xff1a; 参考开源的mqtt-LabVIEW https://github.com…
阅读更多...
PostGIS学习教程七：关于几何图形的练习

PostGIS学习教程七：关于几何图形的练习

文章目录 一、函数列表二、练习 一、函数列表 以下是我们迄今为止看到的所有函数的汇总&#xff0c;它们应该对练习有用&#xff01; sum(expression) aggregate to return a sum for a set of records count(expression) aggregate to return the size of a set of records …
阅读更多...
JAVA G1垃圾收集器介绍

JAVA G1垃圾收集器介绍

为解决CMS算法产生空间碎片和其它一系列的问题缺陷&#xff0c;HotSpot提供了另外一种垃圾回收策略&#xff0c;G1&#xff08;Garbage First&#xff09;算法&#xff0c;通过参数-XX:UseG1GC来启用&#xff0c;该算法在JDK 7u4版本被正式推出&#xff0c;官网对此描述如下&am…
阅读更多...
JS-项目实战-更新水果单价更新小计更新总计

JS-项目实战-更新水果单价更新小计更新总计

1、fruit.js //当页面加载完成后执行后面的匿名函数 window.onload function () {//get:获取 Element:元素 By:通过...方式//getElementById()根据id值获取某元素let fruitTbl document.getElementById("fruit_tbl");//table.rows:获取这个表格的所有的行&a…
阅读更多...
目标检测—Yolo系列（YOLOv1/2/v3/4/5/x/6/7/8）

目标检测—Yolo系列（YOLOv1/2/v3/4/5/x/6/7/8）

目标检测概述 什么是目标检测&#xff1f; 滑动窗口&#xff08;Sliding Window&#xff09; 滑动窗口的效率问题和改进 滑动窗口的效率问题&#xff1a;计算成本很大 改进思路 1&#xff1a;使用启发式算法替换暴力遍历 例如 R-CNN&#xff0c;Fast R-CNN 中使用 Selectiv…
阅读更多...
S32DS踩坑日记五-bootloader跳转APP时触发DefaultISR

S32DS踩坑日记五-bootloader跳转APP时触发DefaultISR

S32DS踩坑日记五-bootloader跳转APP时触发DefaultISR bootloader和APP由另一位同事开发过程中&#xff0c;被导师叫回去写论文了。 由于项目不急&#xff0c;接手后未作任何改动&#xff0c;后面硬件工程师手工焊了几块电路版&#xff0c;需要刷上程序测试电路板。然后就遇到了…
阅读更多...
最新文章

Copyright @ 2022~2023