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

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

相关内容

热门资讯

原生的安卓系统 索尼,深度解析... 你知道吗？在智能手机的世界里，有一个品牌总是以其独特的魅力和精湛的工艺吸引着众多科技爱好者。那就是索...
安卓系统更新历史,从初代到最新... 你有没有发现，你的安卓手机每次更新后都变得焕然一新？没错，这就是安卓系统更新带来的魔力！今天，就让我...
安卓系统的第二套系统,创新与变... 你知道吗？在科技飞速发展的今天，安卓系统已经成为了智能手机市场上的霸主。但是，你知道吗？安卓系统其实...
全军出击安卓系统版本,战力再攀... 你有没有发现，最近全军出击这款游戏在安卓系统上的版本更新可是越来越频繁了呢？这不，我就来给你好好扒一...
安卓系统热点限速软件,优化热点... 你有没有遇到过这种情况：手机连接热点后，网速就像蜗牛爬行一样慢，简直让人抓狂！别急，今天就来给你揭秘...
安卓系统占内存多,揭秘内存消耗... 你有没有发现，手机用着用着，内存就不够用了？尤其是安卓系统，好像特别能吃内存，让人头疼不已。今天，就...
最近安卓系统奔溃,揭秘原因与应... 最近手机界可是炸开了锅呢！安卓系统竟然出现了大规模奔溃，这可真是让人摸不着头脑。咱们一起来探究这背后...
ce系统能刷安卓系统吗,揭秘能... 你有没有想过，你的安卓手机是不是也能用上CE系统呢？这可不是天方夜谭，今天就来给你揭秘一下这个神秘的...
安卓系统UI设计特色,创新与用... 你有没有发现，每次打开安卓手机，那界面设计得真是让人眼前一亮呢？今天，就让我带你一起探索一下安卓系统...
ipod有安卓系统吗,跨界融合... 你有没有想过，那个曾经风靡一时的iPod，它到底有没有安卓系统呢？这个问题，估计让不少音乐爱好者都好...
安卓多少系统最高的,揭秘最高版... 你有没有想过，你的安卓手机到底升级到了哪个系统版本呢？是不是好奇安卓系统里哪个版本才是最高级的呢？别...
现在安卓最高的系统,揭秘安卓1... 你有没有发现，手机更新换代的速度简直就像坐上了火箭呢！这不，最近安卓系统又来了一次大升级，听说这是现...
安卓系统怎么隐藏相册,安卓系统... 你是不是也有那么几本“私人珍藏”，不想让旁人随意翻看呢？比如，手机里的相册，里面藏着我们的喜怒哀乐，...
安卓桌面挂件系统下载,下载与个... 你有没有发现，手机桌面上的那些小玩意儿，简直就是生活的调味品？今天，咱们就来聊聊安卓桌面挂件系统下载...
wp手机加安卓系统,探索跨界新... 你有没有想过，为什么你的手机总是那么卡，而别人的手机却流畅得像风一样？是不是觉得自己的手机有点OUT...
省电手机推荐安卓系统,安卓系统... 手机这玩意儿，对于我们这些手机控来说，简直就是生活的必需品。但是，你知道吗？现在市面上那么多手机，要...
安卓系统衰落怎么恢复,探寻衰落... 你有没有发现，最近安卓系统好像有点儿“水土不服”了呢？曾经的霸主地位，如今似乎有些动摇。不过别急，今...
安卓系统手机应用锁,安全无忧的... 你有没有发现，现在手机里的秘密越来越多，是不是也跟小秘密一样，想要找个地方藏起来呢？没错，今天就要来...
安卓系统书院源app,安卓系统... 你有没有发现，手机里的安卓系统越来越智能了？今天，我要给你介绍一个特别有意思的书院源app，它可是安...
安卓系统8.1平板推荐,安卓8... 你有没有想过，拥有一款性能卓越、体验流畅的安卓系统8.1平板，简直就是移动办公和娱乐的完美搭档？没错...