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

相关内容

热门资讯

自动打开应用安卓系统,安卓系统... 你有没有想过,手机里的那些应用,有时候真是让人又爱又恨呢?有时候,我们急需某个应用,却得费老大力气去...
安卓系统防沉迷软件,守护青少年... 你有没有发现,现在手机上玩游戏的诱惑力简直让人无法抗拒?尤其是安卓系统,那丰富的游戏资源,简直让人停...
流量最快的安卓系统,揭秘流量最... 你有没有想过,为什么你的手机总是那么卡,而别人的手机却像开了挂一样流畅?是不是好奇,为什么有些安卓系...
小米5换换安卓系统,畅享极致性... 你有没有想过,你的小米5手机,那个陪伴你走过无数日夜的小家伙,是不是也该给它来个“换新装”了呢?没错...
国产的安卓系统手机,畅享智能生... 你有没有发现,最近国产的安卓系统手机越来越火了?没错,就是那种咱们自己研发的系统,那种让外国品牌都不...
安卓系统刷入停止,探究原因与解... 你有没有遇到过这种情况?手机刷机过程中突然停止了,安卓系统刷入停滞不前,心里那个急啊!别慌,今天就来...
汽车是安卓系统嘛,安卓系统在智... 你有没有想过,汽车里那个神奇的操作系统,是不是和安卓手机里的一样呢?没错,今天咱们就来聊聊这个话题—...
网易狼人杀 安卓系统,体验指尖... 亲爱的玩家们,你是否曾在深夜里,手机屏幕前,与一群好友展开一场惊心动魄的“狼人杀”对决?今天,就让我...
小米安卓系统小主机,探索小米安... 你有没有想过,家里的电视、电脑、平板,甚至手机,其实都可以变成一个超级智能的娱乐中心?没错,这就是小...
卡刷安卓系统大全,全面解析各类... 你有没有想过,你的安卓手机可以像变形金刚一样,随心所欲地变换模样?没错,今天就要给你揭秘一个神奇的世...
安卓系统测试流畅度,安卓系统流... 你有没有发现,现在手机更新换代的速度简直就像坐上了火箭呢!尤其是安卓系统,每次更新都让人眼前一亮。但...
安卓系统50怎么升级,轻松迈向... 亲爱的安卓用户们,你是否也像我一样,对安卓系统的更新充满了期待?没错,就是那个让我们的手机焕然一新的...
安卓5.1.1操作系统,系统特... 你知道吗?在手机世界里,操作系统就像是个大管家,它不仅决定了手机的脸面,还掌管着手机的所有“家务事”...
手机安卓系统如果升级,体验流畅... 亲爱的手机控们,你们有没有发现,你的安卓手机最近是不是总在提醒你更新系统呢?别急,别急,今天就来给你...
安卓系统怎么禁止待机,安卓系统... 手机待机时间短,是不是让你头疼不已?别急,今天就来教你一招,让你的安卓手机告别“短命”模式,延长待机...
亿联安卓苹果系统,跨平台沟通新... 你知道吗?在科技飞速发展的今天,手机操作系统可是咱们日常生活中不可或缺的一部分。说起手机系统,亿联安...
smoothx安卓系统安装ap... 你有没有想过,为什么你的手机里总是乱糟糟的,各种app堆在一起,找起来费劲得很?别急,今天就来教你怎...
安卓系统图库在哪里,图库应用位... 你有没有发现,手机里的照片越来越多,有时候想找一张特定的照片,却像大海捞针一样困难?别急,今天就来告...
安卓7.0系统自带彩蛋,隐藏彩... 你知道吗?安卓7.0系统里竟然藏着不少小秘密,就像一颗颗隐藏的彩蛋,等着我们去发现。今天,就让我带你...
安卓系统好用的电池,好用到飞起... 你有没有发现,用安卓手机的时候,电池续航能力简直让人爱不释手啊!没错,今天咱们就来聊聊这个话题——安...