考研算法35天:三元组的最小距离 【双指针,滑动窗口,多路归并】

这篇具有很好参考价值的文章主要介绍了考研算法35天:三元组的最小距离 【双指针,滑动窗口,多路归并】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

算法详解

多路归并;多路归并算法从理论到应用(易懂)_留恋单行路的博客-CSDN博客

多路归并就是将多个已经归并排序排好序的数组再进行排序(不一定是通过归并排序)。

算法题目

考研算法35天:三元组的最小距离 【双指针,滑动窗口,多路归并】,算法

这道题就是一般做法是先通过排序将三个数组排好然后再进行三指针求最小。但是我们仔细考虑一下,如果我们先将这三个数组排好序那么势必需要额外开一个数组,那么空间复杂度就变成了O(N)。如果我们在排序的同时去取最小距离呢?我们就不需要开一个额外的数组了。 但是那样咋做呢?我们来模拟一下吧。

假如现在我们已经找到三个点了,分别是a,b,c;那么我们如何求例题中那个式子的最小值呢?其实我们可以将例题中的式子换一下。就变成了len = 2 * (max(a,b,c) - min(a,b,c)).如下图

考研算法35天:三元组的最小距离 【双指针,滑动窗口,多路归并】,算法 

然后,继续:那么我们如何才能找到那三个指针呢?我认为只需要三个指针每次如果谁小于等于其他两个指针就算一次res(式子的值)=(max - min)*2。然后将最小的那个指针向后移动(目的:减小三个指针之间的值)。

#include <iostream>
using namespace std;

const int N = 100010; 
long long int a[N];
long long int b[N];
long long int c[N];

int main(){
    long long int  l,n,m;
    cin>>l>>n>>m;
    for(int i=0;i<l;i++)cin>>a[i];
    for(int i=0;i<n;i++)cin>>b[i];
    for(int i=0;i<m;i++)cin>>c[i];
    
    long long int res = 1e18;
    int i,j,k;
    long long int x,y,z;
    for( i=0,j=0,k=0;i<l&&j<n&&k<m;){
        x=a[i], y=b[j], z=c[k];
        res = min(res,max(x,max(y,z)) - min(x,min(y,z)));
        if(x<=y&&x<=z) i++;
        else if(y<=x&&y<=z) j++;
        else k++;
    }
    cout<<res*2;
    return 0;
}文章来源地址https://www.toymoban.com/news/detail-527479.html

到了这里,关于考研算法35天:三元组的最小距离 【双指针,滑动窗口,多路归并】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 面试算法35:最小时间差

    给定一组范围在00:00至23:59的时间,求任意两个时间之间的最小时间差。例如,输入时间数组[“23:50”,“23:59”,“00:00”],\\\"23:59\\\"和\\\"00:00\\\"之间只有1分钟的间隔,是最小的时间差。 这个题目最直观的解法是求出任意两个时间的间隔,然后比较得出最小的时间差。如

    2024年02月06日
    浏览(42)
  • Leetcode18-算术三元组的数目(2367)

    给你一个下标从 0 开始、严格递增 的整数数组 nums 和一个正整数 diff 。如果满足下述全部条件,则三元组 (i, j, k) 就是一个 算术三元组 : i j k , nums[j] - nums[i] == diff 且 nums[k] - nums[j] == diff 返回不同 算术三元组 的数目。 示例 1: 输入:nums = [0,1,4,6,7,10], diff = 3 输出:2 解释:

    2024年02月02日
    浏览(33)
  • 数据结构:三元组的构建、相加和快速转置

    目录 1.三元组表的定义 2.三元组表的数据结构 3.三元组表的构建 4.输出三元组表 5.两个三元组表相加  代码的流程图​  实现代码 6.三元组表的快速转置  算法思想  代码实现 7.三元组表输出矩阵 8.全部代码 9.总结         三元组研究目的 对于在实际问题中出现的大型的

    2024年02月02日
    浏览(36)
  • 考研算法复试刷题19天:Prim算法求最小生成树 【prim,最小生成树】

    参考博客:图解:什么是最小生成树? - 知乎 (zhihu.com)  总结下来的过程就是,一张图,我们将他化为树的形式,也就是生成树。那么最小生成树有是啥呢? 所谓一个 带权图 的最小生成树,就是原图中边的权值最小的生成树 ,所谓最小是指边的权值之和小于或者等于其它

    2024年02月07日
    浏览(60)
  • 【Python】值得收藏,三元一次方程组的计算,快来看看有什么新奇的~~~

    三元一次方程组的计算对于大家来说都不陌生了,但是用编程语言来解决方程组问题想必还是会有些大聪明们有点迷糊的,今天就带大家来看看是怎么利用python实现方程组的解集的; 本文主要分成两部分: 解题 验算 综述 代码 结果 [[ 3 0 4] [ 2 3 1] [ 5 -9 7]] [7 9 8] 计算结果:

    2024年02月01日
    浏览(36)
  • 【算法专题突破】滑动窗口 - 长度最小的子数组(9)

    目录 1. 题目解析 2. 算法原理 3. 代码编写 写在最后: 题目链接:209. 长度最小的子数组 - 力扣(Leetcode)  要注意的是,题目给的是正整数, 而题目要求并不难理解,就是找最短的子数组。 如果使用暴力的话,就是一个O(N3)的算法,复杂度很高, 我们可以用滑动窗口来做,

    2024年02月09日
    浏览(31)
  • 算法刷题记录-双指针/滑动窗口(LeetCode)

    思路 根据题目描述,我们可以知道,如果要将某个单词定义为可扩张(stretchy),需要满足如下两个条件: 所以,我们在实现的时候,可以通过两个指针p1和p2,分别指向s和word,分别统计连续的相同字符数量c1和c2,然后再通过上述的两个条件进行判断,即:如果 则表示该单

    2024年02月09日
    浏览(41)
  • 【算法|滑动窗口No.1】leetcode209. 长度最小的子数组

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月08日
    浏览(41)
  • 每日OJ题_算法_滑动窗口⑧_力扣76. 最小覆盖子串

    目录 力扣76. 最小覆盖子串 解析及代码 76. 最小覆盖子串 - 力扣(LeetCode) 难度 困难 给你一个字符串  s  、一个字符串  t  。返回  s  中涵盖  t  所有字符的最小子串。如果  s  中不存在涵盖  t  所有字符的子串,则返回空字符串  \\\"\\\"  。 注意: 对于  t  中重复字符,

    2024年01月23日
    浏览(40)
  • 255.【华为OD机试】最小矩阵宽度(滑动窗口算法-Java&Python&C++&JS实现)

    🚀点击这里可直接跳转到本专栏,可查阅顶置最新的华为OD机试宝典~ 本专栏所有题目均包含优质解题思路,高质量解题代码(JavaPythonC++JS分别实现),详细代码讲解,助你深入学习,深度掌握!

    2024年03月13日
    浏览(62)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包