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

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

相关内容

热门资讯

黑陶蛋壳套膳具：用餐更有趣 小编今天要向大家介绍一款独特的膳具，那就是食物语黑陶蛋壳套膳具！这款套膳具不仅外观别致，而且功能多样...
Win8本地连接消失，怎么办？... 最近，许多Win8系统用户遇到了一个令人困扰的问题：本地连接消失了。当你想要连接网络时Win8本地连...
萌新必看！琉生传前期流程推荐！ 琉生传是一款热门的角色扮演游戏，吸引了众多玩家的关注。对于刚刚入坑的萌新玩家来说，了解游戏的前期流程...
Win10 1903：让你办公... Win101903是微软公司最新推出的操作系统版本之一，它带来了许多新功能和改进。然而，有时我们可能...
ADSL拨号错误代码大全，泪目... ADSL拨号，我们生活中不可或缺的一项技术。然而，有时候我们会遇到各种各样的问题，让人欲哭无泪。小编...
Win10专业版系统激活问题解... 微软的Windows10操作系统是目前最受欢迎和广泛使用的操作系统之一。而在众多版本中，Win10专...
Linux下线程同步方法，让程... 标题：线程同步线程同步的方法有哪些？Linux下实现线程同步的三，让程序跳起来！ 小编来告诉大...
Win8本地连接消失，咋办？快... Win8系统是微软公司推出的一款操作系统，具有简洁、稳定的特点，深受用户喜爱。然而，有时我们在使用W...
Win10系统重装后激活问题，... 重装Win10系统是很常见的操作，但有时候在重新安装后，我们可能会遇到无法激活的问题。下面小编将介绍...
足球梦工厂：挑选未来之星的攻略... 小编认为，足球梦工厂是一个寻找未来之星的殿堂。在这个神奇的工厂里，每一位球员都有机会成为巨星。但要想...
汉尼拔巴卡：万国觉醒的超级英雄 汉尼拔巴卡万国觉醒汉尼拔巴卡使用心得，这个名字听起来就像是一个非常厉害的角色，让人忍不住想要了解他的...
修复英特尔CPU漏洞，简单操作... 小编教你如何修改注册表来禁用英特尔CPU的幽灵/熔断/僵尸负载漏洞修改注册表禁用英特尔CPU幽灵/熔...
IE浏览器重新安装，让上网更畅... 小编教你如何重新安装IE浏览器如何重新安装IE浏览器，保证让你的上网体验更畅快！（系统词库） ...
ADSL拨号错误代码大全，快速... ADSL拨号是一种常见的上网方式ADSL拨号中出现的错误代码大全，但在使用过程中可能会遇到各种错误代...
琉生传：萌新上手指南，玩转前期... 琉生传，一款风靡全球的多人在线角色扮演游戏。对于刚入坑的萌新来说，可能会感到有些迷茫，不知道从何开始...
Win10专业版系统，Micr... 小编听说有一种神奇的工具，叫做MicroKMS激活工具，据说它能让Win10专业版系统焕发新生！你是...
1999元！米手机5现场上手体... 米手机5现场上手体验标配版仅仅1999元 小编亲临米手机5发布会现场，亲身感受了这款备受期待的...
电脑键盘快捷键：高效办公秘籍！ 【標題】掌握高效技巧電腦鍵盤快捷鍵大全，提升辦公效率——電腦鍵盤快捷鍵大全 【內容】 在...
Win10 2019年5月更新... 小编教你一键永久激活Win102019年5月更新版，让你的操作系统顺畅运行，享受最新功能。无需复杂步...
Host表：域名与IP的映射奥... Host表：解析域名与IP地址的映射 小编很高兴为大家介绍一下host表，也许你对它还不太熟悉...