【c++leetcode】35. Search Insert Position

问题入口

二分搜索

时间复杂度O(logn)

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int start = 0;
        int end = nums.size() - 1;

        while (start <= end)
        {
            int mid = (start + end) / 2;
            if (nums[mid] == target)
            {
                return mid;
            }
            else if(nums[mid] > target)
            {
                end = mid - 1;
            }
            else if(nums[mid] < target)
            {
                start = mid + 1;
            }
            
        }
        
        return start;
    }
};

由于给到的数组是从小到大的,可以使用二分搜索法,即以中间的元素为界,如果大于中间元素,范围限定在右半边,如果小于中间元素,范围限定在左半边。假设数组元素数为n,范围依次是n\rightarrow \frac{n}{2}\rightarrow \frac{n}{4}\rightarrow ...\rightarrow 1。假设通过k次找到指定元素, \frac{n}{2^{k}} = 1, k=log_{2}n。时间复杂度为O(logn)

时间复杂度O(n)

class Solution {
public:
    //O(n)
    int searchInsert(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); i++)
        {
            if (nums[i] == target)
                return i;
            else
            {
                if (nums[i] > target)
                    return i;
                else
                    continue;
                
            }
        }
        return nums.size();
    }
};

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

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

相关文章

Axure如何调起浏览器的打印功能

Axure如何调起浏览器的打印功能 答&#xff1a;javascript:window.print(); 不明白的继续往下看 应用场景&#xff1a; 原型设计中&#xff0c;页面上的打印按钮&#xff0c;需要模拟操作演示&#xff0c;需要点击指定的按钮时&#xff0c;唤起浏览器的打印功能&#xff08…

QT httpServer多线程后台服务器的例子实现

1.需求 1.1 用户需要其他平台&#xff08;web端&#xff09;调用Qt平台的接口&#xff0c;获取想要的数据并实时显示在网页里&#xff0c;比如实时的温湿度&#xff0c;用户数据等 1.2 用户需要在其他平台&#xff08;web端&#xff09;调用Qt平台的接口&#xff0c;下发数据…

使用 GitHub Actions 实现项目的持续集成(CI)

目录 什么是 GitHub Actions 基础概念 Workflow 文件 Workflow 语法 实例&#xff1a;编译 OpenWrt 什么是 GitHub Actions GitHub Actions 是 GitHub 推出的持续集成&#xff08;Continuous Integration&#xff0c;简称 CI&#xff09;服务它允许你创建自定义工作流&am…

【webrtc】MessageHandler 3: 基于线程的消息处理:以sctp测试为例

消息处理可以用于模拟发包处理G:\CDN\rtcCli\m98\src\net\dcsctp\socket\dcsctp_socket_network_test.cc 这个实现中,onMessage还是仅对了一种消息进行处理,就是接收则模式下,打印带宽。当然,可能程序有多个消息,分别在不同的onmessage中执行?SctpActor:以一个恒定的速率…

【webrtc】MessageHandler 1: 基于线程的消息处理:以10毫秒处理音频为例

基于m98 G:\CDN\rtcCli\m98\src\audio\null_audio_poller.h分发的消息由MessageHandler 类通过其抽象接口OnMessage 实现处理 NullAudioPoller NullAudioPoller 是一个处理audio的消息的分发器 poll 启动:

Adobe Firefly 3.0 AI 图像生成器来了

Adobe 发布其 Midjourney 和 Dall-E 3 竞争对手Firefly 2.0已经半年了。几天前&#xff0c;他们发布了Firefly 3.0&#xff08;目前处于测试阶段&#xff09;&#xff0c;这是他们最新的文本到图像人工智能工具&#xff0c;其中包含一些非常酷的更新。在我们深入了解细节之前&a…

开发一个语音聊天社交app小程序H5需要多少钱?

社交&#xff0c;即时通讯APP系统。如何开发一个社交App||开发一个即时通信应用是一项复杂而充满挑战的任务&#xff0c;需要考虑多个技术、开发时间和功能方面的因素。以下是一个概要&#xff0c;描述了从技术、开发时间和功能角度如何开发这样的应用&#xff1a; 1. 技术要点…

Docker-compose的介绍与用法

Docker-compose Docker Compose 是一个开源的容器编排工具&#xff0c;由 Docker 官方开发。它允许开发者定义一个或多个 Docker 容器作为单个服务&#xff0c;并将这些服务组合成一个项目。这些定义被保存在一个 YAML 文件中&#xff0c;称为 docker-compose.yml。 使用 Dock…

低代码技术在构建质量管理系统中的应用与优势

引言 在当今快节奏的商业环境中&#xff0c;高效的质量管理系统对于组织的成功至关重要。质量管理系统帮助组织确保产品或服务符合客户的期望、符合法规标准&#xff0c;并持续改进以满足不断变化的需求。与此同时&#xff0c;随着技术的不断进步&#xff0c;低代码技术作为一…

Qt下使用7Z源码进行压缩和解压缩

7Z压缩是一款常用的压缩算法和工具&#xff0c;本文主要介绍一款在qt环境下进行编译的压缩方法。 本人测试是可以正常跑通的&#xff0c;具体代码部分请下载&#xff1a;下载链接&#xff0c;提取码&#xff1a;ev9t 7z源码网址&#xff1a;7-Zip 7z简介&#xff1a; 7z 是…

一文带你了解5款高效率软件,建议收藏

​ 人类与99%的动物之间最大差别在于是否会运用工具&#xff0c;借助好的工具&#xff0c;能提升几倍的工作效率。 1. 高速文件复制——TeraCopy ​ TeraCopy是一款高效的文件复制工具&#xff0c;可以大幅度提高文件复制和移动的速度。它支持多线程复制、错误恢复、校验和等…

2024-04学习笔记

1.sql优化-子查询改为外连接 1.改之前 改之前是这样&#xff0c;那针对查出来的每一条数据&#xff0c;都要执行一次箭头所指的函数 执行的sql很慢 2.改之后 改之后是这样&#xff0c;整体做外连接&#xff0c;不用每一条都再执行一次查询 执行时间缩短了好几倍 2.Mybatis中…

maven修改默认编码格式为UTF-8

执行mvn -version查看maven版本信息发现&#xff0c;maven使用的编码格式为GBK。 为什么想到要修改编码格式呢&#xff1f;因为idea中我将文件格式统一设置为UTF-8&#xff08;如果不知道如何修改文件编码&#xff0c;可以参考文末&#xff09;&#xff0c;然后使用maven打包时…

ubuntu22 部署fastDFS单节点和集群,整合Spring Boot(刚部署成功)

ubuntu22 部署fastDFS单节点和集群 一、先准备1、所需依赖安装2、下载安装包 二、安装FastDFS单节点1、libfastcommon安装1.1、创建软连接 2、安装fastDFS2.1、fastDFS目录简单介绍2.2、创建软连接 3、配置和启动Tracker服务3.1、修改Tracker配置文件3.2、启动Tracker 4、配置和…

字节码插桩 -- 入门篇

背景 我们先了解下什么情况下会用到字节码插桩。学技术并不是为了秀技术&#xff0c;而是为了解决业务问题。 我们先想象一个业务场景— 我们需要统计耗时方法&#xff0c;这时&#xff0c;我们会怎么做&#xff1f; 在每个方法开头和结尾处分别记录开始时间与结束时间&…

学生管理系统[Python语言]

各位大佬好 &#xff0c;这里是阿川的博客 &#xff0c; 祝您变得更强 个人主页&#xff1a;在线OJ的阿川 大佬的支持和鼓励&#xff0c;将是我成长路上最大的动力 阿川水平有限&#xff0c;如有错误&#xff0c;欢迎大佬指正 学生管理系统是计算机专业最基础的一个作业&#…

高扬程水泵,提升水源新选择!— 恒峰智慧科技

在炎炎夏日&#xff0c;阳光炙烤着大地&#xff0c;森林火灾的发生频率也随之上升。火势猛烈&#xff0c;烟雾弥漫&#xff0c;给森林带来了极大的破坏。为了保护森林资源&#xff0c;我们必须采取有效的措施来扑灭火灾。而在这其中&#xff0c;高扬程水泵成为了提升水源新选择…

智慧旅游驱动行业革新:智能技术引领服务全面升级,匠心打造高品质、个性化旅游新体验

一、引言 随着科技的飞速发展和信息化程度的不断提高&#xff0c;智慧旅游正逐渐成为旅游业发展的新趋势。智慧旅游&#xff0c;顾名思义&#xff0c;是以智能化技术为支撑&#xff0c;通过大数据、云计算、物联网、人工智能等先进技术的应用&#xff0c;实现旅游服务的全面升…

Java项目:基于SSM框架实现的实践项目管理系统(ssm+B/S架构+源码+数据库+毕业论文+开题报告)

一、项目简介 本项目是一套基于SSM框架实现的实践项目管理系统&#xff0c;主要针对计算机相关专业的正在做毕设的学生与需要项目实战练习的Java学习者。 包含&#xff1a;项目源码、数据库脚本等&#xff0c;该项目附带全部源码可作为毕设使用。 项目都经过严格调试&#xff…

BIMBase浏览器新功能——碰撞检测

BIMBase浏览器&#xff08;原BIMBase建模软件 Lite&#xff09;全新R1.14版本已经全面上线&#xff0c;新版本下载链接&#xff1a;BIMBase浏览器R1.14。本次给大家介绍一下本次版本的重点功能&#xff1a;碰撞检测。 各位设计院/施工单位/运维单位的伙伴们在模型交付、方案讨论…