Leetcode—4.寻找两个正序数组的中位数【困难】

2023每日刷题(二十九)

Leetcode—4.寻找两个正序数组的中位数

在这里插入图片描述

直接法实现代码

int mid, mid1, mid2;
bool findmid(int n, int k, int x) {
    if(n % 2 == 1) {
        if(k == n / 2) {
            mid = x;
            return true;
        }
    } else {
        if(k == n / 2 - 1) {
            mid1 = x;
        } else if(k == n / 2) {
            mid2 = x;
            return true;
        }
    }
    return false;
}

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int n = nums1Size + nums2Size;
    int i = 0, j = 0, k = 0;
    bool flag = false;
    while(i < nums1Size && j < nums2Size) {
        if(nums1[i] < nums2[j]) {
            flag = findmid(n, k, nums1[i]);
            if(flag) {
                break;
            }
            i++;
        } else {
            flag = findmid(n, k, nums2[j]);
            if(flag) {
                break;
            }
            j++;
        }
        k++;
    }
    while(i < nums1Size && !flag) {
        flag = findmid(n, k, nums1[i]);
        k++;
        i++;
    }
    while(j < nums2Size && !flag) {
        flag = findmid(n, k, nums2[j]);
        k++;
        j++;
    }
    if(n % 2 == 1) {
        return mid;
    } else {
        return (mid1 + mid2) / 2.0;
    }
}

运行结果

在这里插入图片描述

优化代码

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int n = nums1Size + nums2Size;
    int mid1 = 0, mid2 = 0;
    int i = 0, j = 0, k = 0;
    while((i < nums1Size || j < nums2Size) && k <= n / 2) {
        if((j >= nums2Size) || (i < nums1Size && nums1[i] <= nums2[j])) {
            if(k == n / 2) {
                mid1 = nums1[i];
            } else if(k == n / 2 - 1) {
                mid2 = nums1[i];
            }
            i++;
        }
        else {
            if(k == n / 2) {
                mid1 = nums2[j];
            } else if(k == n / 2 - 1) {
                mid2 = nums2[j];
            }
            j++;
        }
        k++;
    }
    if(n % 2 == 1) {
        return mid1;
    } else {
        return (mid1 + mid2) / 2.0;
    }
}

运行结果

在这里插入图片描述

二分法算法思想——降低时间复杂度到题目要求的 O ( l o g ( m + n ) ) O(log(m + n)) O(log(m+n))

其实就是第 k 小数解法,详情参考这篇文章
在这里插入图片描述

二分法实现代码

#define MIN(a, b) ((a < b) ? (a): (b))
int binaryKth(int* nums1, int nums1Size, int* nums2, int nums2Size, int k) {
    int idx1 = 0, idx2 = 0;
    int newIdx1 = 0, newIdx2 = 0;
    int n1 = 0, n2 = 0;
    while(1) {
        if(idx1 == nums1Size) {
            return nums2[idx2 + k - 1];
        }
        if(idx2 == nums2Size) {
            return nums1[idx1 + k - 1];
        }
        if(k == 1) {
            return MIN(nums1[idx1], nums2[idx2]);
        }
        newIdx1 = MIN(idx1 + k / 2 - 1, nums1Size - 1);
        newIdx2 = MIN(idx2 + k / 2 - 1, nums2Size - 1);
        n1 = nums1[newIdx1];
        n2 = nums2[newIdx2];
        if(n1 <= n2) {
            k -= newIdx1 - idx1 + 1;
            idx1 = newIdx1 + 1;
        } else {
            k -= newIdx2 - idx2 + 1;
            idx2 = newIdx2 + 1;
        }
    }
}

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int n = nums1Size + nums2Size;
    if(n % 2 == 1) {
        return binaryKth(nums1, nums1Size, nums2, nums2Size, (n + 1) / 2);
    } else {
        int a = binaryKth(nums1, nums1Size, nums2, nums2Size, n / 2);
        int b = binaryKth(nums1, nums1Size, nums2, nums2Size, n / 2 + 1);
        return (a + b) / 2.0;
    }
}

运行结果

在这里插入图片描述
之后我会持续更新,如果喜欢我的文章,请记得一键三连哦,点赞关注收藏,你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 !!!↖(▔▽▔)↗感谢支持!

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

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

相关文章

3DMAX渲染AO图的三种方法

3DMAX渲染AO图的三种方法 使用Mental Ray渲染AO 1. 我为这个演示制作了一个非常简单的场景。该场景包含一个茶壶、一个盒子和一个球体。我还应用了一些材质&#xff0c;并将渲染引擎设置为Mental Ray。 2. 我还在场景中添加并定位了几个泛光灯。 3. 我选择了Mental Ra…

主题讲座:全球增材制造现状与未来(暨香港科技大学广州|智能制造学域2024博士学位全额奖学金项目)

时间&#xff1a;2023 年11月16日&#xff08;星期四&#xff09;14:30 地点&#xff1a;合肥工业大学 学术会议中心三楼报告厅 主讲嘉宾&#xff1a;陈模军 助理教授 https://facultyprofiles.hkust-gz.edu.cn/faculty-personal-page/CHEN-Mojun/mjchen 报名表直达&#xff1…

数字化时代,企业如何增加产品销售额

2023作为提振消费年&#xff0c;国民宏观经济环境正在复苏&#xff0c;而数字化技术的进步也使消费者的购买方式发生了翻天覆地的变化&#xff0c;对于企业而言&#xff0c;应该如何顺势而上增加产品销售额&#xff0c;成为其成功的关键。 今天媒介盒子就来和大家聊聊企业如何…

DVWA - 3

文章目录 XSS&#xff08;Dom&#xff09;lowmediumhighimpossible XSS&#xff08;Dom&#xff09; XSS 主要基于JavaScript语言进行恶意攻击&#xff0c;常用于窃取 cookie&#xff0c;越权操作&#xff0c;传播病毒等。DOM全称为Document Object Model&#xff0c;即文档对…

笔试题之指针和数组的精讲

&#x1d649;&#x1d65e;&#x1d658;&#x1d65a;!!&#x1f44f;&#x1f3fb;‧✧̣̥̇‧✦&#x1f44f;&#x1f3fb;‧✧̣̥̇‧✦ &#x1f44f;&#x1f3fb;‧✧̣̥̇:Solitary-walk ⸝⋆ ━━━┓ - 个性标签 - &#xff1a;来于“云”的“羽球人”。…

谁输了,就往衣服里面倒水,欲望秀场与亲密的操控,当一位女博士生成为主播

在澎湃新闻上&#xff0c;读到香港大学博士生王怡霖的一篇自述文章。 为了研究秀场直播&#xff0c;她跟一家公会签约&#xff0c;当了秀场主播。 感谢王怡霖&#xff0c;愿意做这样的研究&#xff0c;为我们提供了解社会现实的一个观察视角。 三年主播体验观察下来&#xff0c…

SPI协议详解

SPI协议详解 文章目录 SPI协议详解前言一、SPI是什么&#xff1f;二、通信原理SPI 通信的 4 种工作模式 总结 前言 好久没写这种协议了&#xff0c;最近正好需要用到&#xff0c;便详细的复习一下。 一、SPI是什么&#xff1f; SPI是串行外设接口&#xff08;Serial Periphe…

25.4 MySQL 函数

1. 函数的介绍 1.1 函数简介 在编程中, 函数是一种组织代码的方式, 用于执行特定任务. 它是一段可以被重复使用的代码块, 通常接受一些输入(参数)然后返回一个输出. 函数可以帮助开发者将大型程序分解为更小的, 更易于管理的部分, 提高代码的可读性和可维护性.函数在编程语言…

苍穹外卖-day10

苍穹外卖-day10 课程内容 Spring Task订单状态定时处理WebSocket来单提醒客户催单 功能实现&#xff1a;订单状态定时处理、来单提醒和客户催单 订单状态定时处理&#xff1a; 来单提醒&#xff1a; 客户催单&#xff1a; 1. Spring Task 1.1 介绍 Spring Task 是Spring框…

剑指 Offer 07. 重建二叉树

title: 剑指 Offer 07. 重建二叉树 tags: 二叉树递归 categories:算法剑指 Offer 题目描述 输入某二叉树的前序遍历和中序遍历的结果&#xff0c;请构建该二叉树并返回其根节点。 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 示例 1: Input: preorder [3,9,…

人工智能与新能源电动车的融合——技术创新引领未来交通革命

人工智能与新能源电动车的融合——技术创新引领未来交通革命 摘要&#xff1a;本文探讨了人工智能与新能源电动车领域的技术融合&#xff0c;分析了其在智能驾驶、电池技术、充电设施等方面的应用与创新。文章指出&#xff0c;这两大技术的结合将重塑交通产业&#xff0c;为我…

PTE-RS 练习(二)

目录 内容分漏多漏少没有什么关系 Write Essay 感知比记忆强的多 记住骨干&#xff0c;剩下脑补 套上有含义的帽子 &#xff0c; 套上了信息就会很牢固 谁在说&#xff0c;为什么会说这句话 听不懂那个文本如何处理 要产生表达欲 会分为很多的块 做好意群分割…

第一百七十二回 SegmentedButton组件

文章目录 1. 概念介绍2. 使用方法2.1 SegmentedButton2.2 ButtonSegment 3. 代码与效果3.1 示例代码3.2 运行效果 4. 内容总结 我们在上一章回中介绍了"SearchBar组件"相关的内容&#xff0c;本章回中将 介绍SegmentedButton组件.闲话休提&#xff0c;让我们一起Tal…

【C++】类和对象(4)--析构函数

一 概念 通过前面构造函数的学习&#xff0c;我们知道一个对象是怎么来的&#xff0c;那一个对象又是怎么没呢的&#xff1f; 析构函数&#xff1a;与构造函数功能相反&#xff0c;析构函数不是完成对对象本身的销毁&#xff0c;局部对象销毁工作是由编译器完成的。而对象在销…

数据库操作入门:PyMongo 和 MongoDB 的基本用法

MongoDB MongoDB是一种流行的NoSQL数据库&#xff0c;它将数据存储在类似JSON的文档中&#xff0c;使数据库非常灵活和可扩展 PyMongo Python需要一个MongoDB驱动程序来访问MongoDB数据库。在本教程中&#xff0c;我们将使用MongoDB驱动程序 “PyMongo”。建议使用PIP来安装…

清理mac苹果电脑磁盘软件有哪些免费实用的?

苹果电脑是一款非常流行的操作系统设备&#xff0c;其稳定性和性能一直备受用户的喜爱。然而&#xff0c;随着时间的推移&#xff0c;我们使用电脑的过程中可能会发现磁盘上存储的数据越来越多&#xff0c;这不仅占用了宝贵的硬盘空间&#xff0c;还可能导致电脑运行变慢。因此…

GreenCloud VPS 重装系统后无法 SSH 的解决方法

发布于 2023-07-17 在 https://chenhaotian.top/vps/greencloud-ssh-fix/ 解决方法 发工单让客服解决即可。 操作过程 Tu Pham Operator 客服 Hello, We have fixed your problem, please try again! Thanks! Tu Pham, Senior Technician - GreenCloudVPS 17th July 2023…

Java Stream 的使用

Java Stream 的使用 开始中间操作forEach 遍历map 映射flatMap 平铺filter 过滤limit 限制sorted 排序distinct 去重 结束操作collect 收集toList、toSet 和 toMapCollectors.groupingByCollectors.collectingAndThen metch 匹配find 查询findFirst 与 findAny 的使用Optional …

Ubuntu 和 Windows 文件互传

FTP 服务 FTP 采用 Internet 标准文件传输协议 FTP 的用户界面&#xff0c; 向用户提供了一组用来管理计算机之间文件传输的应用程序。在开发的过程中会频繁的在 Windows 和 Ubuntu 下进行文件传输&#xff0c;比如在 Windwos 下进行代码编写&#xff0c;然后将编写好的代码拿到…

计算机操作系统—经典同步问题

经典同步问题 1.生产者与消费者问题 1.1.问题概述 在现实生活中&#xff0c;当我们缺少某些生活用品时&#xff0c;就会到超市去购买。当你到超市时&#xff0c;你的身份就是消费者&#xff0c;那么这些商品又是哪里来的呢&#xff0c;自然是供应商&#xff0c;那么它们就是生…