【算法】数组之二分查找移除元素
admin
2024-01-31 06:35:40
0次

目录

1、数组理论基础

2、二分查找

 2.1 区间左闭右闭写法

2.2 区间左闭右开写法 

 3、移除元素

3.1  暴力解法

3.2 双指针（快慢指针）法

1、数组理论基础

参考以前的博客：http://t.csdn.cn/HAVSF

2、二分查找

力扣https://leetcode.cn/problems/binary-search/

【题目】给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

【参考代码】 

int search(int* nums, int numsSize, int target){int left = 0;int right = numsSize - 1;while(left<=right){int mid = left+(right-left)/2;if(nums[mid]>target){right = mid-1;}else if(nums[mid]

首先关于这个二分查找法，主要有两个易错点，一个是while循环条件里面的符号究竟是小于等于还是小于。另一个是if—else if—else里面的判断体究竟需不需要进行加一减一的操作。

要解决这个问题还是从问题本身出发，那就是没有搞清楚区间的定义，而定义过的区间就是固定的，即“不变量”。每一次循环里面的处理都需要根据区间来选择，这也是为什么有时候有些题加一减一似乎对其没什么影响，但有时候又必须加一或者减一。

下面给出二分法写法的两个版本：

 2.1 区间左闭右闭写法

int search(int* nums, int numsSize, int target){int left = 0;int right = numsSize - 1;while(left<=right){int mid = left+(right-left)/2;//int mid = (left+right)/2;//int mid = left+(right-left)>>1;if(nums[mid]>target){right = mid-1;}else if(nums[mid]

在这种情况下，target是定义在[left,right]上的，此时left=right是有意义的，注意这里跟数学里面的区间定义不同，因为有意义，所以此时while(left<=right),如果你少写=，会有值被你漏算。除此之外，你还需要注意一下if判断体里面是否需要加一或减一，如果nums[mid]>target,说明当前的nums[mid]一定不是target,所以更新后的搜索右下标范围为mid-1。

2.2 区间左闭右开写法 

int search(int* nums, int numsSize, int target){int left = 0;int right = numsSize;while(lefttarget){right = mid;}else if(nums[mid]

在这种情况下，target是定义在[left,right)上的，此时left=right是没有意义的，因为没有意义，所以此时while(lefttarget,说明当前的nums[mid]一定不是target,而右区间本就是开区间，所以更新后的搜索右下标范围为mid。但nums[mid]

【相关题目训练】

1.力扣https://leetcode.cn/problems/search-insert-position/
2.力扣https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/3.力扣https://leetcode.cn/problems/sqrtx/4.力扣https://leetcode.cn/problems/valid-perfect-square/

 3、移除元素

力扣https://leetcode.cn/problems/remove-element/

【题目】给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

【思路】要知道数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。

以下给出两个方法： 

3.1  暴力解法

//两个for循环，一个for遍历整个数组元素，另一个更新数组元素
int removeElement(int* nums, int numsSize, int val){for(int i=0;i

在本代码中：

  • 时间复杂度：O(n^{2})
  • 空间复杂度：O(1)

3.2 双指针（快慢指针）法

通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

定义快慢指针：

  • 寻找新数组的元素 ，新数组就是不含有目标元素的数组
  • 指向更新后新数组下标的位置
int removeElement(int* nums, int numsSize, int val){int slow = 0;for(int fast =0;fast

 在本代码中：

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

 【本题小结】显然法二明显优于法一，双指针法在数组和链表的操作中是很常见的，很多数组链表OJ题都可以使用双指针法解决。

【相关题目训练】 

力扣https://leetcode.cn/problems/remove-duplicates-from-sorted-array/

力扣https://leetcode.cn/problems/move-zeroes/

力扣https://leetcode.cn/problems/backspace-string-compare/

力扣https://leetcode.cn/problems/squares-of-a-sorted-array/

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：C++11多线程thread使用详解

下一篇：哈希思想的应用 - 位图，布隆过滤器

相关内容

热门资讯

122.（leaflet篇）l... 听老人家说：多看美女会长寿 地图之家总目录（订阅之前建议先查看该博客） 文章末尾处提供保证可运行...
育碧GDC2018程序化大世界... 1.传统手动绘制森林的问题 采用手动绘制的方法的话，每次迭代地形都要手动再绘制森林。这...
育碧GDC2018程序化大世界... 1.传统手动绘制森林的问题 采用手动绘制的方法的话，每次迭代地形都要手动再绘制森林。这...
Vue使用pdf-lib为文件... 之前也写过两篇预览pdf的，但是没有加水印，这是链接：Vu...
PyQt5数据库开发1 4.1... 文章目录 前言 步骤/方法 1 使用windows身份登录 2 启用混合登录模式 3 允许远程连接服...
Android studio ... 解决 Android studio 出现“The emulator process for AVD ...
Linux基础命令大全（上） ♥️作者：小刘在C站 ♥️个人主页：小刘主页 ♥️每天分享云计算网络运维...
再谈解决“因为文件包含病毒或潜... 前面出了一篇博文专门来解决“因为文件包含病毒或潜在的垃圾软件”的问题，其中第二种方法有...
南京邮电大学通达学院2023c... 题目展示 一.问题描述 实验题目1 定义一个学生类，其中包括如下内容： （1）私有数据成员 ①年龄 ...
PageObject 六大原则 PageObject六大原则： 1.封装服务的方法 2.不要暴露页面的细节 3.通过r...
【Linux网络编程】01：S... Socket多进程 OVERVIEWSocket多进程1.Server2.Client3.bug&...
数据结构刷题（二十五）：122... 1.122. 买卖股票的最佳时机 II思路：贪心。把利润分解为每天为单位的维度,然后收...
浏览器事件循环 事件循环 浏览器的进程模型 何为进程？ 程序运行需要有它自己专属的内存空间࿰...
8个免费图片/照片压缩工具帮您... 继续查看一些最好的图像压缩工具，以提升用户体验和存储空间以及网站使用支持。 无数图像压...
计算机二级Python备考（2... 目录  一、选择题 1.在Python语言中： 2.知识点 二、基本操作题 1. j...
端电压 相电压 线电压 记得刚接触矢量控制的时候，拿到板子，就赶紧去测各种波形，结...
如何使用Python检测和识别... 车牌检测与识别技术用途广泛，可以用于道路系统、无票停车场、车辆门禁等。这项技术结合了计...
带环链表详解 目录 一、什么是环形链表 二、判断是否为环形链表 2.1 具体题目 2.2 具体思路 2.3 思路的...
【C语言进阶：刨根究底字符串函... 本节重点内容： 深入理解strcpy函数的使用学会strcpy函数的模拟实现⚡strc...
Django web开发(一)... 文章目录前端开发1.快速开发网站2.标签2.1 编码2.2 title2.3 标题2.4 div和s...