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

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

相关内容

热门资讯

苹果表有安卓系统时间,时间同步... 你有没有发现，最近苹果表也开始支持安卓系统了？没错，就是那个一直以封闭著称的苹果，竟然也开始拥抱安卓...
原生安卓系统裁剪图片,原生安卓... 你有没有发现，用原生安卓系统拍照，有时候拍出来的照片分辨率超高，但就是有点大，想裁剪却不知道怎么操作...
安卓系统蓝牙开关APP,安卓系... 你有没有遇到过这种情况：手机里的安卓系统蓝牙开关总是让人摸不着头脑？有时候想开蓝牙，却找不到开关在哪...
安卓系统能登录ios系统王者吗... 你有没有想过，安卓系的手机能不能登录iOS系统的王者荣耀呢？这可是个让人好奇不已的问题哦！毕竟，两个...
苹果和安卓系统文件怎么,系统架... 你有没有想过，为什么你的手机里那么多乱糟糟的文件，有时候找起来还真是头疼？今天，就让我来给你好好捋一...
安卓系统9.0稳定版,深度解析... 你知道吗？最近安卓系统9.0稳定版可是火得一塌糊涂呢！这款系统不仅带来了全新的功能和优化，还让无数安...
安卓系统目录结构网盘,安卓系统... 你有没有想过，你的安卓手机里那些看似杂乱无章的文件，其实背后隐藏着一个有序的目录结构呢？今天，就让我...
安卓系统在哪里买专辑,专辑购买... 你有没有想过，手机里那熟悉的安卓系统，竟然也能帮你买到心仪的专辑呢？没错，就是那个让你随时随地畅享音...
鸿蒙系统离开了安卓吗,迈向独立... 你有没有听说最近鸿蒙系统的大动作？没错，就是那个让安卓和iOS都紧张起来的操作系统。今天，咱们就来聊...
安卓系统耗电本地视频,本地视频... 手机电量总是不够用，是不是你也和我一样，对安卓系统的耗电问题头疼不已？尤其是当你想看个本地视频放松一...
手机安卓最好的系统是,揭秘最佳... 你有没有想过，为什么你的手机用起来有时候那么顺畅，有时候又那么卡顿呢？这背后其实和手机系统有着千丝万...
怎么拍镜像照片安卓系统,如何拍... 摄影爱好者们，你是否曾对那些在水中倒影中捕捉到的美丽瞬间感到着迷？想要在安卓手机上也能轻松拍出这样的...
安卓7运行xp系统,兼容性与性... 你有没有想过，把一个古老的操作系统装在现代的安卓设备上？想象安卓7系统下运行Windows XP，这...
戴尔安卓系统升级,解锁无限可能 你有没有发现，你的戴尔安卓设备最近是不是变得有点儿不一样了？没错，就是那个戴尔安卓系统升级，它就像一...
安卓系统怎么变苹果主题,打造苹... 你有没有想过，把你的安卓手机变成苹果风格的呢？想象那光滑的界面、简洁的图标，是不是瞬间觉得高大上了？...
系统进程有病毒吗安卓,安卓安全... 你有没有想过，你的安卓手机里那些忙碌的系统进程，它们会不会突然生病了呢？没错，我说的就是病毒！今天，...
编程安卓系统和鸿蒙主题,跨平台... 你有没有想过，手机的世界里，除了苹果的iOS和安卓的操作系统，还有个神秘的鸿蒙系统？今天，咱们就来聊...
哪个安卓机系统好用,探索安卓系... 你有没有想过，手机里的安卓系统就像是个大厨，不同的系统就像不同的烹饪手法，有的让你吃得津津有味，有的...
安卓如何控制苹果系统,从安卓到... 你知道吗？在这个科技飞速发展的时代，安卓和苹果两大操作系统之间的较量从未停歇。虽然它们各自有着忠实的...
安卓原生系统文件夹,安卓原生系... 你有没有发现，每次打开安卓手机，里面那些文件夹就像是一个个神秘的宝箱，里面藏着各种各样的宝贝？今天，...