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

相关内容

热门资讯

想买华为但是安卓系统,尽享安卓... 最近是不是也被华为的新款手机给迷住了?看着那流畅的线条和强大的性能,是不是心动了呢?但是,一想到安卓...
怎么拷安卓系统文件,安卓系统文... 你有没有想过,手机里的那些安卓系统文件,其实就像是一扇通往手机世界的秘密通道呢?想要深入了解你的安卓...
安卓系统移植按键失灵,安卓系统... 最近你的安卓手机是不是也遇到了按键失灵的尴尬情况呢?这可真是让人头疼啊!别急,今天就来给你详细解析一...
安卓系统更新管理在哪,全面解析... 你有没有发现,你的安卓手机最近是不是总在提醒你更新系统呢?别急,别急,今天就来手把手教你,安卓系统更...
安卓系统哪里出的,从诞生地到全... 你有没有想过,我们每天离不开的安卓系统,它究竟是从哪里冒出来的呢?是不是觉得这个问题有点儿像是在问星...
最好的电脑安卓系统,最佳电脑安... 亲爱的电脑迷们,你是否在寻找一款既能满足你工作需求,又能让你畅享娱乐的电脑操作系统呢?今天,我要给你...
安卓系统保密性,守护隐私的坚实... 你知道吗?在这个信息爆炸的时代,保护个人隐私变得比以往任何时候都重要。尤其是对于安卓系统用户来说,了...
苹果系统下载安卓版本,安卓版本... 你有没有想过,为什么苹果系统的手机那么受欢迎,却还有人想要下载安卓版本呢?这背后可是有着不少故事呢!...
安卓系统如何下载carplay... 你是不是也和我一样,对安卓系统上的CarPlay功能充满了好奇?想象在安卓手机上就能享受到苹果Car...
退回安卓系统的理由,揭秘安卓系... 你有没有想过,为什么有些人会选择退回到安卓系统呢?这可不是一件简单的事情,背后可是有着不少原因哦!让...
安卓机系统互通吗,共创智能生态 你有没有想过,你的安卓手机里的应用和电脑上的安卓应用是不是可以无缝对接呢?是不是有时候觉得手机上的某...
安卓源码 添加系统应用,系统应... 你有没有想过,手机里的那些系统应用是怎么来的?是不是觉得它们就像天外来物,神秘又神奇?其实,只要你愿...
安卓系统能否播放flv,全面解... 你有没有想过,你的安卓手机里那些珍贵的FLV视频文件,到底能不能顺利播放呢?这可是个让人挠头的问题,...
奔驰c系安卓系统,智能驾驶体验... 你有没有发现,最近开奔驰C系的小伙伴们都在悄悄地谈论一个新玩意儿——安卓系统!没错,就是那个我们手机...
安卓系统打印服务名称,探寻打印... 你有没有发现,手机里的安卓系统里有一个神奇的小功能,那就是打印服务!没错,就是那个可以让你把手机里的...
安卓系统主界面切换,探索个性化... 你有没有发现,每次打开安卓手机,那主界面切换的瞬间,就像是打开了一扇通往新世界的大门呢?今天,就让我...
安卓系统xml是什么,Andr... 你有没有想过,你的手机里那些看起来平平无奇的图标和布局,其实背后有着一套复杂的“语言”在支撑呢?没错...
魔盒正版安卓系统下载,畅享极致... 亲爱的读者们,你是否曾梦想拥有一款纯净无瑕的安卓系统,就像打开了一个神秘的魔盒,里面蕴藏着无尽的惊喜...
苹果安卓系统销量,系统销量争霸... 你有没有发现,最近手机圈里有个大热门话题,那就是苹果和安卓系统的销量大战!没错,就是那个让无数手机爱...
谷歌系统恢复软件安卓,轻松实现... 手机突然卡壳了,是不是你也遇到了这样的尴尬情况?别急,今天就来聊聊如何让你的安卓手机重获新生——谷歌...