【算法】数组之二分查找移除元素
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收音机,尽享无线音域 你有没有想过，在安卓手机上，除了刷剧、聊天、玩游戏，还能干点啥？今天，就让我带你一探究竟，看看安卓系...
安卓怎么退回老系统,安卓系统升... 手机用久了，是不是觉得新系统越来越卡，老系统那个熟悉的感觉又回来了？别急，今天就来教你怎么把安卓手机...
安卓系统44限制吗 最近你的安卓手机是不是突然感觉有点儿“力不从心”了呢？别急，让我来给你揭秘一下安卓系统44的限制之谜...
闪回门店系统安卓版,焕新零售体... 你有没有想过，那些曾经陪伴我们度过无数美好时光的门店，现在是不是还留在你的记忆里呢？今天，就让我带你...
安卓系统和windows同步,... 你有没有发现，手机里的照片、文档、音乐，还有那些重要的联系人信息，有时候真是让人头疼，因为它们都分散...
安卓系统在哪儿开源,从诞生到全... 你有没有想过，安卓系统这个我们每天不离手的家伙，它到底是从哪儿来的呢？没错，就是开源！今天，就让我带...
三星安卓系统711,探索创新与... 你有没有发现，最近手机圈里又掀起了一股热潮？没错，就是三星的新款手机，搭载的安卓系统7.1.1。这可...
安卓系统应用无法启动,探究无法... 手机里的安卓系统应用突然打不开，是不是让你心头一紧？别急，今天就来给你详细解析一下这个问题，让你轻松...
安卓主题仿苹果系统吗,探索苹果... 你有没有发现，最近手机界又掀起了一股风潮？那就是安卓手机上的主题设计，竟然开始模仿苹果系统的风格了！...
安卓系统盒马餐饮熟食,安卓系统... 你有没有发现，现在的生活越来越离不开手机了？尤其是安卓系统，几乎成了我们生活中不可或缺的一部分。这不...
thinkpad8安卓双系统,... 你有没有想过，一台笔记本电脑既能满足你工作时的严谨需求，又能让你在闲暇时刻畅游安卓世界？今天，就让我...
想看安卓系统u青年影院,U青年... 亲爱的读者们，你是否也和我一样，对安卓系统的电影应用充满了好奇？今天，就让我带你一起探索一个特别的地...
安卓系统王者荣耀更新慢,探究原... 最近你是不是也遇到了这个问题？每次打开王者荣耀，总是慢吞吞的，让人等得心痒痒。安卓系统的王者荣耀更新...
安卓系统怎么装ios系统软件,... 你是不是也和我一样，对安卓系统上的iOS软件垂涎欲滴呢？想象在安卓手机上流畅运行《王者荣耀》或者《原...
蓝牙系统和安卓哪个好使,谁更胜... 蓝牙系统和安卓哪个好使？这个问题，相信不少手机用户都曾纠结过。蓝牙系统，作为无线通信技术的一种，让我...
安卓系统停用怎么回事 最近你的安卓手机是不是突然有点儿“闹脾气”了？屏幕上突然弹出一个通知，告诉你安卓系统要停用了？别急，...
安卓系统照片怎么发视频 你是不是也和我一样，手机里存了好多珍贵的照片，突然想和朋友们分享一段美好的回忆呢？别急，今天就来教你...
永远会用安卓系统的手机 亲爱的手机控们，你是否也有那么一款手机，它陪伴你度过了无数个日夜，成为了你生活中不可或缺的一部分？没...