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

相关内容

热门资讯

安卓系统相机不能启动,安卓相机... 手机里的安卓系统相机突然不能启动了,这可真是让人头疼啊!你有没有遇到过这种情况呢?别急,今天就来跟你...
安卓原生系统时间校准,基于安卓... 手机时间不准了?别急,我来教你如何轻松搞定安卓原生系统时间校准! 话题引入:手机时间不准,是不是让你...
主机系统内存和安卓联机,主机系... 你有没有想过,为什么你的手机在玩大型游戏时总是卡得要命?又或者,为什么你的电脑在处理复杂任务时,反应...
安卓如何手机上刷系统,轻松升级... 你有没有想过,你的安卓手机是不是已经有点儿“老态龙钟”了呢?别急,别急,今天就来教你怎么给它来个“青...
苹果系统观战安卓好友,观战新体... 亲爱的读者,你是否也有过这样的经历:一边享受着苹果系统的优雅与流畅,一边又忍不住好奇地观战安卓好友们...
安卓系统最好是哪个,最佳生成方... 你有没有想过,手机里的安卓系统哪个才是最适合你的呢?在这个信息爆炸的时代,手机已经成为了我们生活中不...
改时间安卓系统vivo,探索v... 你有没有发现,最近你的vivo手机有点儿“慢吞吞”的?别急,别急,让我来给你支个招儿,让你的安卓系统...
安卓系统的旋钮在哪,旋钮生成位... 你有没有发现,有时候手机上的小细节也能让人头疼不已?比如说,安卓系统的旋钮在哪?这问题看似简单,但不...
安卓手机app系统软件,探索安... 你有没有发现,现在手机里的app简直就像是个小宇宙,各种功能应有尽有,让人眼花缭乱。尤其是安卓手机,...
win111安卓子系统,开启跨... 哇,你有没有听说最近的大新闻?那就是Windows 11的安卓子系统!是的,你没听错,Windows...
游戏摇杆连安卓系统电视,畅享游... 你有没有想过,家里的安卓系统电视也能玩起游戏来?没错,就是那种让你手舞足蹈、热血沸腾的游戏摇杆!今天...
nokia平板系统兼容安卓,尽... 你有没有想过,那些曾经陪伴我们度过无数时光的诺基亚手机,现在竟然也能摇身一变,成为平板电脑的得力助手...
安卓原生系统是什么品牌,探索安... 你有没有想过,为什么你的手机那么流畅,界面那么美观?这背后,可是有一个强大的“大脑”在默默支撑着呢!...
安卓3大操作系统,从三大分支看... 你知道吗?在安卓的世界里,操作系统可是有着三大巨头呢!它们就像安卓世界的三驾马车,各自有着独特的魅力...
开源文件管理系统安卓,打造个性... 你有没有想过,手机里那些乱糟糟的文件,要是能有个好帮手,生活该有多轻松啊?今天,就让我带你走进一个神...
手机删除了系统安卓市场,手机系... 手机里的安卓市场突然不见了,这可怎么办呢?别急,让我来给你详细说说这个棘手的问题,让你轻松应对!一、...
安卓系统写脚本软件下载,基于安... 你有没有想过,你的安卓手机或者平板电脑,除了用来刷剧、玩游戏,还能变成一个强大的工作助手呢?没错,就...
安卓系统有哪些机型好,探索顶级... 你有没有想过,安卓系统里的手机型号那么多,哪一款才是最适合你的呢?别急,今天我就来给你好好盘点看看安...
安卓系统之间如何互传,安卓设备... 你是不是也和我一样,手机里存了那么多好东西,却苦于不能和好友分享呢?别急,今天就来教你怎么用安卓系统...
安卓系统启动修改工具,安卓系统... 你有没有想过,你的安卓手机启动速度竟然可以像火箭一样快?没错,这就是今天我要跟你分享的神秘工具——安...