【算法】数组之二分查找移除元素
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使用详解

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

相关内容

热门资讯

【MySQL】锁 锁 文章目录锁全局锁表级锁表锁元数据锁（MDL）意向锁AUTO-INC锁...
【内网安全】 隧道搭建穿透上线... 文章目录内网穿透-Ngrok-入门-上线1、服务端配置：2、客户端连接服务端ÿ...
GCN的几种模型复现笔记 引言 本篇笔记紧接上文，主要是上一篇看写了快2w字，再去接入代码感觉有点...
数据分页展示逻辑 import java.util.Arrays;import java.util.List;impo...
Redis为什么选择单线程？R... 目录专栏导读一、Redis版本迭代二、Redis4.0之前为什么一直采用单线程？三、R...
【已解决】ERROR: Cou... 正确指令： pip install pyyaml
关于测试，我发现了哪些新大陆 关于测试 平常也只是听说过一些关于测试的术语，但并没有使用过测试工具。偶然看到编程老师...
Lock 接口解读 前置知识点Synchronized synchronized 是 Java 中的关键字，...
Win7 专业版安装中文包、汉... 参考资料：http://www.metsky.com/archives/350.htm...
3 ROS1通讯编程提高(1) 3 ROS1通讯编程提高3.1 使用VS Code编译ROS13.1.1 VS Code的安装和配置...
大模型未来趋势 大模型是人工智能领域的重要发展趋势之一，未来有着广阔的应用前景和发展空间。以下是大模型未来的趋势和展...
python实战应用讲解-【n... 目录 如何在Python中计算残余的平方和 方法1：使用其Base公式 方法2：使用statsmod...
学习u-boot 需要了解的m... 一、常用函数 1. origin 函数 origin 函数的返回值就是变量来源。使用格式如下...
常用python爬虫库介绍与简... 通用 urllib -网络库(stdlib)。 requests -网络库。 grab – 网络库&...
药品批准文号查询|药融云-中国... 药品批文是国家食品药品监督管理局（NMPA）对药品的审评和批准的证明文件...
【2023-03-22】SRS... 【2023-03-22】SRS推流搭配FFmpeg实现目标检测 说明： 外侧测试使用SRS播放器测...
有限元三角形单元的等效节点力 文章目录前言一、重新复习一下有限元三角形单元的理论1、三角形单元的形函数（Nÿ...
初级算法-哈希表 主要记录算法和数据结构学习笔记，新的一年更上一层楼！ 初级算法-哈希表...
进程间通信【Linux】 1. 进程间通信 1.1 什么是进程间通信 在 Linux 系统中，进程间通信...
【Docker】P3 Dock... Docker数据卷、宿主机与挂载数据卷的概念及作用挂载宿主机配置数据卷挂载操作示例一个容器挂载多个目...