PAT甲级-1029 Median

题目

题目大意

给定两个递增序列,求这两个序列合并为一个递增序列后的中位数。

思路

直接用一个数组接收两个数组的输入,然后用sort()暴力求解,也可以过,但是时间复杂度较高。

更好的方法是双指针法,两个数组各一个指针来依次遍历,用一个count计数是否遍历到了中间位置,注意奇数个和偶数个的中间位置不一样。统一起来的表达式就是 (n1 + n2) / 2 + (n1 + n2) % 2 - 1。

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    long long n1, n2;
    cin >> n1;
    vector<long long> v1(n1);
    for (long long i = 0; i < n1; i++){
        cin >> v1[i];
    }
    cin >> n2;
    vector<long long> v2(n2);
    for (long long i = 0; i < n2; i++){
        cin >> v2[i];
    }

    long long i = 0, j = 0, m, mpos, count = 0;
    mpos = (n1 + n2) / 2 + (n1 + n2) % 2 - 1; // 如果是偶数,/2后-1,如果奇数,/2
    while (i < n1 && j < n2 && count <= mpos){
        if (v1[i] < v2[j]){
            m = v1[i];
            i++;
        }else{
            m = v2[j];
            j++;
        }
        count++;
    }
    while (i < n1 && count <= mpos){
        m = v1[i];
        i++;
        count++;
    }
    while(j < n2 && count <= mpos){
        m = v2[j];
        j++;
        count++;
    }
    cout << m << endl;

    return 0;
}  // 双指针法

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

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

相关文章

在线plotly绘制动态旭日图,展示复杂数据层次结构

探索数据的层次之美&#xff1a;旭日图&#xff0c;以环环相扣的视觉效果&#xff0c;清晰展现数据的层级关系。搭配Plotly的动态可视化技术&#xff0c;不仅让数据层次一目了然&#xff0c;更通过交互式操作&#xff0c;让用户轻松探索每个层级的详细信息&#xff0c;享受数据…

解决移动端1px 边框优化的8个方法

前言 您是否注意到 1px 边框在移动设备上有时会显得比预期的要粗&#xff1f;这种不一致源于移动屏幕的像素密度不同。 在 Web 开发中&#xff0c;我们使用 CSS 来设置页面样式。但是&#xff0c;CSS 中的 1px 并不总是转换为设备上的物理 1px。这种差异就是我们的“1px 边框…

如何在网上找客户资源

在网上寻找客户资源可以通过多种渠道和方法来实现&#xff0c;这些方法结合不同的工具和平台&#xff0c;可以帮助你快速定位目标客户。以下是一些常见且有效的途径&#xff1a; 1. 利用搜索引擎 使用搜索引擎&#xff08;如百度、Google&#xff09;通过关键词搜索目标客户或…

JAVA一键开启缘分之旅红娘相亲交友系统小程序源码

一键开启缘分之旅 —— 红娘相亲交友系统 &#x1f496; 初遇心动&#xff0c;一键启程 在这个快节奏的时代&#xff0c;找到那个对的人似乎成了一种奢侈。但别担心&#xff0c;有了“红娘相亲交友系统”&#xff0c;你的缘分之旅只需一键即可开启&#xff01;无需复杂的注册流…

张雪峰:物联网行业迎高光时刻!如何选择?我们诚聘销售工程师!

作为一间10多年的物联网公司&#xff0c;各位求职人士可以看看我们其中一个招聘要求&#xff0c;和自己需求结合分析分析&#xff0c;希望对你们有所帮助。 【公司实力底蕴】 盈电智控物联网科技&#xff08;广东&#xff09;有限公司&#xff0c;2024年7月成立&#xff0c;是…

git pull之后发现项目错误,如何回到之前的版本方法

目录 首先我们打开小程序的cmd的黑窗口&#xff0c;git reflog查看之前的版本 之后再git reset --hard main{1} 我这个就已经返回了之前的6daaa2e的版本了 首先我们打开小程序的cmd的黑窗口&#xff0c;git reflog查看之前的版本 之后再git reset --hard main{1} 我这个就已…

深度学习的发展历程

深度学习的起源 在机器学习中&#xff0c;我们经常使用两种方式来表示特征&#xff1a;局部表示&#xff08;Local Representation&#xff09;和分布式表示&#xff08;Distributed Representation&#xff09;。以颜色表示为例&#xff0c;见下图&#xff1a; 要学习到一种好…

自动驾驶ADAS算法--使用MATLBA和UE4生成测试视频

原文参考&#xff1a;金书世界 环境搭建参考&#xff1a;用MATLAB2020b和虚拟引擎&#xff08;Unreal Engine&#xff09;联合仿真输出AVM全景测试视频----Matlab环境搭建 matlab参考&#xff1a; https://ww2.mathworks.cn/help/driving/ug/simulate-a-simple-driving-sce…

分库分表核心理念

文章目录 分库&#xff0c;分表&#xff0c;分库分表什么时候分库&#xff1f;什么时候分表&#xff1f;什么时候既分库又分表&#xff1f;横向拆分 & 纵向拆分 分表算法Range 范围Hash 取模一致性 Hash斐波那契散列 严格雪崩标准&#xff08;SAC&#xff09;订单分库分表实…

导入word模板的数据到DB,偏自学,可自改套用

GetMapping("/importTestPeople")public void importTestPeople(RequestParam("file") MultipartFile multipartFile) throws IOException {InputStream inputStream null;File file null;try {// 创建临时文件file File.createTempFile("temp&quo…

从0开始深入理解并发、线程与等待通知机制

1、 从0开始深入理解并发、线程与等待通知机制 从上面两大互联网公司的招聘需求可以看到&#xff0c;大厂的Java岗的并发编程能力属于标配。 而在非大厂的公司&#xff0c;并发编程能力也是面试的极大加分项&#xff0c;而工作时善用并发编程则可以极大提升程序员在公司的技术…

前向渲染路径

1、前向渲染路径处理光照的方式 前向渲染路径中会将光源分为以下3种处理方式&#xff1a; 逐像素处理&#xff08;需要高等质量处理的光&#xff09;逐顶点处理&#xff08;需要中等质量处理的光&#xff09;球谐函数&#xff08;SH&#xff09;处理&#xff08;需要低等质量…

phpmyadmin报错mysqli::real_connect(): (HY000/1045): Access denied for user ‘

问题分析 这是因为本身还安装了MySQL&#xff0c;导致发生冲突&#xff0c;只需要找到自己安装的进行关闭即可 方法 在任务管理器(快捷键&#xff1a;ctrlaltdelete)-服务中&#xff0c;找到对应的MySQL进行关闭

爬虫 可视化 管理:scrapyd、Gerapy、Scrapydweb、spider-admin-pro、crawllab、feaplat、XXL-JOB

1、scrapyd 大多数现有的平台都依赖于 Scrapyd&#xff0c;这将选择限制在 python 和 scrapy 之间。当然 scrapy 是一个很棒的网络抓取框架&#xff0c;但是它不能做所有的事情。 对于重度 scrapy 爬虫依赖的、又不想折腾的开发者&#xff0c;可以考虑 Scrapydweb&#xff1b;…

基于springboot+vue实现的在线商城系统

系统主要功能&#xff1a; &#xff08;1&#xff09;商品管理模块&#xff1a;实现了商品的基本信息录入、图片上传、状态管理等相关功能。 &#xff08;2&#xff09;商品分类模块&#xff1a;实现了分类的增删改查、分类层级管理、商品分类的关联等功能。 &#xff08;3&…

基于 SpringBoot 的私人健身与教练预约管理系统

专业团队&#xff0c;咨询送免费开题报告&#xff0c;大家可以来留言。 摘 要 随着信息技术和网络技术的飞速发展&#xff0c;人类已进入全新信息化时代&#xff0c;传统管理技术已无法高效&#xff0c;便捷地管理信息。为了迎合时代需求&#xff0c;优化管理效率&#xff0c;…

【机器学习】高斯网络的基本概念和应用领域以及在python中的实例

引言 高斯网络&#xff08;Gaussian Network&#xff09;通常指的是一个概率图模型&#xff0c;其中所有的随机变量&#xff08;或节点&#xff09;都遵循高斯分布 文章目录 引言一、高斯网络&#xff08;Gaussian Network&#xff09;1.1 高斯过程&#xff08;Gaussian Proces…

idea如何配置模板

配置生成代码指令模板 注&#xff1a;我们常用的有sout,main等指令 第一步打开设置面板 1)按如下操作 2&#xff09;或者CtrlAltS快捷键直接弹出 第二步找 Editor>LiveTemplates 第三步创建模板 步骤如下 1&#xff09;创建分组名字 2)分组名字 3&#xff09;创建自己的模板…

计算机网络与Internet应用

一、计算机网络 1.计算机网络的定义 网络定义&#xff1a;计算机网络是指将地理位置不同的具有独立功能的多台计算机及其外部设备&#xff0c;通过通信线路连接起来&#xff0c;在网络操作系统&#xff0c;网络管理软件及网络通信协议的管理和协调下&#xff0c;实现资源共享…

国产芯片LT8619C:HDMI转RGB/LVDS转换器,4k x 2k 30Hz高分辨率

以下为LT8619C转换芯片的简介&#xff0c;如有不足或错误&#xff0c;请指正&#xff1a; LT8619C是一款高性能HDMI/双模DP接收器芯片&#xff0c;符合HDMI 1.4规范。支持TTL或LVDS信号输出&#xff0c;TTL输出时&#xff0c;可支持输出RGB、BT656、BT1120信号&#xff0c;输出…