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

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

相关内容

热门资讯

安卓用的是什么系统,深度解析A... 你有没有想过，你的安卓手机里到底装的是什么系统呢？是不是觉得这个问题有点儿深奥，其实它背后隐藏着手机...
安卓系统如何改定位苹果,安卓系... 你有没有想过，你的安卓手机竟然可以模仿苹果的定位功能？没错，就是那种精准到让你仿佛置身于苹果用户世界...
安卓系统不能删除软件吗,为何无... 你是不是也遇到过这种情况：手机里装了好多软件，可就是找不到删除它们的办法？别急，今天就来聊聊这个让人...
鸿蒙系统属于安卓么,揭秘其与安... 你有没有想过，手机里的那个鸿蒙系统，它到底是不是安卓的“亲戚”呢？这个问题，估计不少手机控都在心里默...
安卓大屏导航恢复系统,重塑流畅... 你有没有发现，手机屏幕越来越大，导航系统也越来越复杂？有时候，我们不小心把安卓大屏导航恢复系统给误删...
国产安卓机哪个系统好用,探索好... 你有没有想过，国产安卓机哪个系统最好用呢？这可是个让人纠结的问题，毕竟每个系统都有它的特色和亮点。今...
安卓11系统操作方法,轻松上手... 你升级到安卓11系统了吗？是不是还在为如何更好地操作这个新系统而烦恼呢？别急，今天我就来给你详细介绍...
安卓2.3系统流畅内存,揭秘内... 你有没有想过，为什么有些老手机还能跑得飞快，而有些新手机却卡得要命？今天，咱们就来聊聊这个话题——安...
支持安卓系统的硬件芯片,引领智... 你有没有发现，现在手机的世界里，支持安卓系统的硬件芯片可是越来越厉害了呢！想象那些小小的芯片，就像魔...
手机安卓系统性价比,性能与价格... 你有没有发现，现在手机市场上安卓系统的手机越来越受欢迎了呢？这不，最近我入手了一款性价比超高的安卓手...
群晖vmm安装安卓系统,群晖V... 亲爱的电脑爱好者们，你是否曾梦想过在群晖NAS上安装安卓系统，享受移动设备的便捷与NAS的强大存储？...
免费的美发会员安卓系统,安卓系... 亲爱的读者们，你是否曾在街头巷尾，被那些免费的美发会员卡吸引得心痒痒？想象不用花一分钱，就能享受到专...
ego华为装安卓系统,开启智能... 你知道吗？最近科技圈可是炸开了锅，因为华为这个巨头竟然要给自家手机装上安卓系统！这可不是什么小打小闹...
安卓系统软件数据,揭秘智能设备... 你知道吗？在这个科技飞速发展的时代，安卓系统软件数据可是个让人又爱又恨的小家伙。它就像一个调皮的精灵...
安卓系统啥文档不能删,安卓系统... 你有没有想过，在你的安卓手机里，有些文档就像是顽皮的小精灵，无论你怎么赶，它们就是赖在那里不肯走呢？...
安卓游戏系统怎么转苹果,安卓游... 你是不是也和我一样，手里拿着安卓手机玩得乐不思蜀，突然有一天，发现了一款超级酷炫的苹果游戏，心痒痒地...
安卓能否刷华为系统版本,揭秘华... 你有没有想过，你的安卓手机能不能刷上华为的系统版本呢？这可是个让人好奇不已的话题呢！想象如果你的安卓...
谷歌最新系统安卓,谷歌带来的颠... 哇，你知道吗？最近谷歌又放大招了！他们推出了全新的操作系统——安卓！这可不是一个小小的更新，而是一次...
鸿蒙系统真的不算安卓吗,引领全... 最近手机圈子里可是热闹非凡呢！尤其是华为的鸿蒙系统，自从发布以来，就一直是大家讨论的焦点。有人说，鸿...
电脑整盘安装安卓系统 你有没有想过，你的电脑除了装Windows系统，还能来个变身大法，变成一个安卓小怪兽呢？没错，今天就...