代码随想录训练营Day1:二分查找与移除元素

本专栏内容为:代码随想录训练营学习专栏,用于记录训练营的学习经验分享与总结。

文档讲解:代码随想录
视频讲解:二分查找与移除元素

💓博主csdn个人主页:小小unicorn
⏩专栏分类:C++
🚚代码仓库:小小unicorn的代码仓库🚚
🌹🌹🌹关注我带你学习编程知识

Day1

  • 二分查找
    • 题目分析
    • 解题思路:
      • 写法一:
      • 写法二:
  • 移除元素
    • 题目分析:
    • 思路:
      • 暴力:
      • 双指针法:
  • 总结:

二分查找

题目分析

题目描述:给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

题目来源:704.二分查找
在这里插入图片描述

解题思路:

这道题目的前提是数组为有序数组,同时题目还强调数组中无重复元素,因为一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的,这些都是使用二分法的前提条件,当大家看到题目描述满足如上条件的时候,可要想一想是不是可以用二分法了。

二分查找涉及的很多的边界条件,逻辑比较简单,但就是写不好。例如到底是 while(left < right) 还是 while(left <= right),到底是right = middle呢,还是要right = middle - 1呢?

大家写二分法经常写乱,主要是因为对区间的定义没有想清楚,区间的定义就是不变量。要在二分查找的过程中,保持不变量,就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作,这就是循环不变量规则。

写二分法,区间的定义一般为两种,左闭右闭即[left, right],或者左闭右开即[left, right)。

写法一:

第一种写法,我们定义 target 是在一个在左闭右闭的区间里,也就是[left, right] 。

在这个区间内要有以下两点:

1.while (left <= right)
要使用 <= 。
这是因为left == right是有意义的,所以使用 <=。

2.if (nums[middle] > target)
那么 right 要赋值为 middle - 1。
这是因为当前这个nums[middle]一定不是target,那么接下来要查找的左区间结束下标位置就是 middle - 1
例如在数组:1,2,3,4,7,9,10中查找元素2,如图所示:
在这里插入图片描述

代码解决:

class Solution 
{
public:int search(vector<int>& nums, int target) {//定义左闭右闭区间int left=0;int right=nums.size()-1;while(left<=right){int middle=left+((right-left)/2);//说明target在左区间if(nums[middle]>target)right=middle-1;//target在右区间else if(nums[middle]<target)left=middle+1;else//找到了return middle;}//未找到目标值return -1;}
};

时间复杂度:O(log n)
空间复杂度:O(1)

写法二:

如果说定义 target 是在一个在左闭右开的区间里,也就是[left, right) ,那么二分法的边界处理方式则截然不同。

有如下两点:

1.while (left < right)
这里使用 <
这是因为left == right在区间[left, right)是没有意义的

2.if (nums[middle] > target)
right 更新为 middle
这是因为当前nums[middle]不等于target,去左区间继续寻找,而寻找区间是左闭右开区间,所以right更新为middle,即:下一个查询区间不会去比较nums[middle]
在数组:1,2,3,4,7,9,10中查找元素2,如图所示:(注意和方法一的区别)
在这里插入图片描述
代码解决:

class Solution {
public:int search(vector<int>& nums, int target) {int left = 0;int right = nums.size(); // 定义target在左闭右开的区间里,即:[left, right)while (left < right) { // 因为left == right的时候,在[left, right)是无效的空间,所以使用 <int middle = left + ((right - left) >> 1);if (nums[middle] > target) {right = middle; // target 在左区间,在[left, middle)中} else if (nums[middle] < target) {left = middle + 1; // target 在右区间,在[middle + 1, right)中} else { // nums[middle] == targetreturn middle; // 数组中找到目标值,直接返回下标}}// 未找到目标值return -1;}
};

移除元素

题目分析:

题目描述:给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。
不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
题目来源:27.移除元素
在这里插入图片描述

思路:

暴力:

两层for循环,一个for循环遍历数组元素 ,第二个for循环更新数组。

// 时间复杂度:O(n^2)
// 空间复杂度:O(1)
class Solution {
public:int removeElement(vector<int>& nums, int val) {int size = nums.size();for (int i = 0; i < size; i++) {if (nums[i] == val) { // 发现需要移除的元素,就将数组集体向前移动一位for (int j = i + 1; j < size; j++) {nums[j - 1] = nums[j];}i--; // 因为下标i以后的数值都向前移动了一位,所以i也向前移动一位size--; // 此时数组的大小-1}}return size;}
};

时间复杂度:O(n^2)
空间复杂度:O(1)

双指针法:

双指针法(快慢指针法): 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
定义快慢指针

快指针:寻找新数组的元素 ,新数组就是不含有目标元素的数组
慢指针:指向更新 新数组下标的位置
在这里插入图片描述

代码解决

class Solution 
{
public:int removeElement(vector<int>& nums, int val) {int slowIndex=0;for(int fastIndex=0;fastIndex<nums.size();fastIndex++){//只要不等于val就往后移动if(val!=nums[fastIndex])nums[slowIndex++]=nums[fastIndex];}return slowIndex;}
};

时间复杂度:O(n)
空间复杂度:O(1)

总结:

在今天,我们通过两道典型例题,知道了什么是二分法,用到了双指针算法思想,希望通过这两道例题,能对双指针和二分法有更深层的理解。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

基于CLIP的图像分类、语义分割和目标检测

OpenAI CLIP模型是一个创造性的突破&#xff1b; 它以与文本相同的方式处理图像。 令人惊讶的是&#xff0c;如果进行大规模训练&#xff0c;效果非常好。 在线工具推荐&#xff1a; Three.js AI纹理开发包 - YOLO合成数据生成器 - GLTF/GLB在线编辑 - 3D模型格式在线转换 - 3D…

算法进阶指南图论 道路与航线

其实再次看这题的时候。想法就是和强连通分量有关&#xff0c;我们很容易发现&#xff0c;题目中所说的双向边&#xff0c;就构成了一个强连通分量&#xff0c;而所谓的单向边&#xff0c;则相当于把强连通分量进行缩点&#xff0c;然后整个图成为了一个DAG&#xff0c;众所周知…

go程序获取工作目录及可执行程序存放目录的方法-linux

简介 工作目录 通常就是指用户启动应用程序时&#xff0c;用户当时所在的文件夹的绝对路径。 如&#xff1a;root用户登录到linux系统后&#xff0c;一顿cd&#xff08;change directory&#xff09;后, 到了/tmp文件夹下。此时&#xff0c;用户要启动某个应用程序&#xff0…

Mybatis-Plus同时使用逻辑删除和唯一索引的问题及解决办法

1 问题背景 在开发中&#xff0c;我们经常会有逻辑删除和唯一索引同时使用的情况。但当使用mybatis plus时&#xff0c;如果同时使用逻辑删除和唯一索引&#xff0c;会报数据重复Duplicate entry的问题。 举例来说&#xff0c;有表user&#xff0c;建立唯一索引&#xff08;u…

Qt实现动态桌面小精灵(含源码)

目录 一、设计思路 二、部分源码演示 三、源码地址 🌈write in front🌈 🧸大家好,我是三雷科技.希望你看完之后,能对你有所帮助,不足请指正!共同学习交流. 🆔本文由三雷科技原创 CSDN首发🐒 如需转载还请通知⚠️ 📝个人主页:三雷科技🧸—CSDN博客 🎁欢…

了解高防服务器的工作原理

在当今互联网时代&#xff0c;网络安全问题日益突出&#xff0c;各种网络攻击层出不穷。为了保护企业的网络安全&#xff0c;高防服务器应运而生。那么&#xff0c;你是否了解高防服务器的工作原理呢?下面就让我们一起来探索一下。 高防服务器是一种能够有效抵御各种网络攻击的…

万界星空科技MES系统软件体系架构及应用

MES系统是数字化车间的核心。MES通过数字化生产过程控制&#xff0c;借助自动化和智能化技术手段&#xff0c;实现车间制造控制智能化、生产过程透明化、制造装备数控化和生产信息集成化。生产管理MES系统主要包括车间管理系统、质量管理系统、资源管理系统及数据采集和分析系统…

C语言编写一个程序采集招聘信息

因为在这里无法详细解释每行代码和步骤。但是&#xff0c;我可以给大家一个使用Python和requests库编写的简单爬虫程序的例子&#xff0c;它可以从网站上获取招聘信息。你可以根据这个例子&#xff0c;将其改写为使用C语言编写的爬虫程序。 import requests# 指定爬虫IP信息 pr…

软件测试|测试方法论—边界值

边界值分析法是一种很实用的黑盒测试用例方法&#xff0c;它具有很强的发现故障的能力。边界值分析法也是作为对等价类划分法的补充&#xff0c;测试用例来自等价类的边界。 这个方法其实是在测试实践当中发现&#xff0c;Bug 往往出现在定义域或值域的边界上&#xff0c;而不…

“锡安主义”贝尔福宣言希伯来抵抗运动犹太启蒙改革运动奋锐党闪米特人雅利安人

目录 “锡安主义” 贝尔福宣言 希伯来抵抗运动 犹太启蒙改革运动 奋锐党 闪米特人 雅利安人 “锡安主义” “锡安主义”是一种政治和民族运动&#xff0c;旨在支持并促进犹太人建立自己的国家并在历史上与宗教上的祖先之地——巴勒斯坦地区建立一个独立的国家。这一运动…

nginx图片资源管理转发

目标: 服务器上面 /home/images 里面作为文件资源管理器 代码: server {listen 80;server_name hello.world.cn;#apple-app和接口的关联文件location ~.*(images/miniapp)*\.(gif|jpg|jpeg|png)$ {root /home/;try_files $uri $uri/ 404;add_header Cache-Control &q…

“第六十四天” 字扩展和位扩展,外部存储器

存储器和CPU的连接; 现在的计算机MAR&#xff0c;MDR通常集成在CPU内部。存储芯片内只需一个普通的寄存器&#xff08;暂存输入&#xff0c;输出数据&#xff09;。 位扩展&#xff0c;字扩展&#xff0c;字位同时扩展&#xff1b; 位扩展&#xff1a; 位扩展的增加的是主存的…

unity【动画】脚本_角色动画控制器 c#

首先创建一个代码文件夹Scripts 从人物角色Player的基类开始 创建IPlayer类 首先我们考虑到如果不挂载MonoBehaviour需要将角色设置成预制体实例化到场景上十分麻烦&#xff0c; 所以我们采用继承MonoBehaviour类的角色基类方法写代码 也就是说这个脚本直接绑定在角色物体…

经典OJ题:随机链表的复制

目录 题目&#xff1a; 本题的解图关键在于画图与看图&#xff01; 思路分析&#xff1a; 方法一&#xff1a;暴力求解法。 方法二&#xff1a;插入法 方法解析&#xff1a; 步骤一、插入 步骤二、 处理每一个copy的randdom指针⭐————重点 步骤三、拆卸节点 代码…

软件测试|iOS 自动化测试——技术方案、环境配置

移动端的自动化测试&#xff0c;最常见的是 Android 自动化测试&#xff0c;我个人觉得 Android 的测试优先级会更高&#xff0c;也更开放&#xff0c;更容易测试&#xff1b;而 iOS 相较于 Android 要安全稳定的多&#xff0c;但也是一个必须测试的方向&#xff0c;这个系列文…

OAuth 2.0实现统一认证

OAuth 2.0协议概念&#xff1a; OAuth 是 Open Authorization 的简写。OAuth 协议为用户资源的授权提供了一个安全的、开放而又简易的标准。与以往的授权方式不同之处是 OAuth 的授权不会使第三方触及到用户的帐号信息&#xff08;如用户名与密码&#xff09;&#xff0c;即第…

开源:特殊的垄断

免责声明&#xff1a;本博客旨在分享我对开源策略的理解和体会&#xff0c;不代表任何组织或机构的立场或观点&#xff0c;也不构成任何商业或投资的建议或担保。本博客的内容可能存在错误或遗漏&#xff0c;也可能随着时间的推移而变得过时或不适用。请在使用或依赖本博客的内…

Google play的企业开发者账号比个人号上包成功率更高?

众所周知&#xff0c;Google play作为全球最大的Android应用市场&#xff0c;是开发者们推广应用的首选平台。Google play平台提供了两种账号类型&#xff1a;个人开发者和企业开发者&#xff0c;开发者们可以选择创建个人开发者账号或者企业开发者账号进行应用上架。 不过&am…

Stable Diffusion WebUI扩展sd-webui-controlnet之Canny

什么是Canny? 简单来说,Canny是计算机视觉领域的一种边缘检测算法。 关于Canny算法大家可以去看我下面这篇博客,里面详细介绍了Canny算法的原理以及代码演示。 OpenCV竟然可以这样学!成神之路终将不远(十五)_maxminval opencv-CSDN博客文章浏览阅读111次。14 图像梯度…