算法-二分查找、移除元素

这篇具有很好参考价值的文章主要介绍了算法-二分查找、移除元素。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

伪装成一个老手!

一、二分查找

题目

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

来源:力扣二分查找

阻碍

1. Q1: 为什么想到要用二分法?
A1: 识别关键词:对有序无重复数组进行查找。二分法顾名思义就是从中间分开,通过中间元素与查询的目标值比较不断缩小区间范围,最终定位元素。
2. Q2:查询区间范围如何表达?
A2:一般区间定义常有左闭右闭“[ ]”,左闭右开‘[ )’两种,使用哪一种都可以,但全程区间的定义要保持不变,不能一会是“[ ]”,过一会又是‘[ )’。这是保证代码逻辑正确性的关键。
3. Q3数组中间值mid, 及左left右right的确定
A3:mid=(left+right)/2, 但一般我们更倾向于使用mid=left+(rigrt-left)/2。尽管在数学运算上mid的计算结果是一样的,但是前者(left+right)的值有可能在计算机中溢出,导致结果错误。
当查询目标值target>num[mid]时,说明target处于右半区间,故需要移动left=mid+1;
当查询目标值target<num[mid]时,说明target处于左半区间,故需要移动right=mid-1 or right=mid-1,我们只需要记住num[mid]已经被判断过了,所以新区间的边界是不应该再包含num[mid]的,所以闭区间“[ ]”right=mid-1,开区间‘[ )’right=mid。

代码

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left=0;
        int right=nums.size()-1;
        while(left<=right)
        {
            int middle=left+(right-left)/2;
            if(nums[middle]>target) {right=middle-1;}
            else if(nums[middle]<target){left=middle+1;}
            else {return middle;}

        }
        return -1;

    }
};

来源:代码随想录

二、移除元素

题目

给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。
不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
示例:

输入:nums = [3,2,2,3], val = 3
输出:2, nums = [2,2]
解释:函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如,函数返回的新长度为 2 ,而 nums = [2,2,3,3] 或 nums = [2,2,0,0],也会被视作正确答案。

来源:力扣移除元素

阻碍

1. Q1:如何删除数组中的元素?
A2:数组存储在一段连续的内存空间,数组中的元素不能被删除,只能被后面的元素覆盖。
2. Q2:数组元素的具体删除操作?
A2:第一步遍历找到目标元素;第二步,目标元素后的元素逐个前移,完成覆盖操作。
3. Q3:什么叫双指针以及两个指针各自的作用?
A3: 双指针就是两个指针(一快一慢),一个指针(快)用来遍历数组寻找目标元素,另一个指针(慢)用来指向更新后数组的当前值。双指针使得原本两层for循环可以减少为一层for循环,降低了时间复杂度。
4. Q4:慢指针如何更新?
A4:满足题目要求是,慢指针停滞(不进行赋值更新),不满足时将快指针赋值慢指针。

代码

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
       int slowIndex=0;
       for(int fastIndex=0; fastIndex<nums.size(); fastIndex++){
         if(val!=nums[fastIndex]){
            nums[slowIndex++]=nums[fastIndex];
          }

        }
        return slowIndex;
    }
};

来源:代码随想录文章来源地址https://www.toymoban.com/news/detail-497939.html

到了这里,关于算法-二分查找、移除元素的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • # - LeetCode 704-二分查找 |LeetCode 27-移除元素

    ##  LeetCode 704-二分查找 -题目描述:给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target , -写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。 给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target  , 写一个函数搜索 nums

    2024年02月16日
    浏览(53)
  • 代码随想录Python:704. 二分查找,27. 移除元素

    数组是非常基础的数据结构。 数组是存放在连续内存空间上的相同类型数据的集合。 题目: 给定一个  n  个元素有序的(升序)整型数组  nums  和一个目标值  target   ,写一个函数搜索  nums  中的  target ,如果目标值存在返回下标,否则返回  -1 。 题目链接:. - 力扣

    2024年02月13日
    浏览(52)
  • Day1 LeetCode 704.二分查找 27.移除元素

    704.二分查找 题目链接: 力扣 文章讲解: 代码随想录 视频讲解: 手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode:704. 二分查找_哔哩哔哩_bilibili 看完随想录之后的想法 两种情况1.左闭右闭  [ ]  2.左闭右开 [ )  当定义时为左闭右闭时,while中if的条件可以

    2024年02月15日
    浏览(40)
  • 代码随想录day1 | 704.二分查找 27.移除元素

    1、循环变量 2、判断条件 当时左闭右闭时,while循环里面的条件,我们可以先假设,有等号即有left=right的情况,例如[1,1]这个区间,那么循环是要进入里面的,所以要取得等号。 判断的时候,nums[mid]tar,那么必然tar不在右半区间,所以right=mid-1 nums[mid]tar,那么必然tar不在左半

    2024年02月15日
    浏览(60)
  • day1-数组part01| 704. 二分查找、27. 移除元素

    数组是存放在连续内存空间上的相同类型数据的集合。 数组下标从0开始 数组内存空间的地址是连续的 1、vector是顺序容器,其利用连续的内存空间来存储元素,但是其 内存空间大小是能够改变的 。 2、array是顺序容器,其也是利用连续的内存空间来存储元素,但它的 内存空

    2024年02月05日
    浏览(46)
  • 代码随想录第一天 | LeetCode704.二分查找,LeetCode 27.移除元素

    数组理论基础要点: 数组也是数据结构的一种, 是存放在连续内存空间上的相同类型数据的集合。 数组注意点: 数组下标都是从0开始的。 数组内存空间的地址是连续的。 因为上述两点, 数组的在内存空间的地址是连续的,所以我们在删除或者增添元素的时候,就难免要

    2024年02月08日
    浏览(50)
  • 二分查找结果总是不对?一文帮你解决二分查找的边界问题&&数组移除元素太耗时间,双指针法为你打开新世界的大门,降时间复杂度为O(n)

      可能有粗心写的不正确的地方,或者因为技术有限写得不好的地方,欢迎大家批评指正,文章中给出的代码是本人自己写的leetcode中的代码,是代码的核心部分,如果放到本地编译器中,可能要加入mian()函数等内容。 LeetCode704二分查找    二分查找的思路非常简单,也就

    2024年02月08日
    浏览(67)
  • 二分查找:34. 在排序数组中查找元素的第一个和最后一个位置

    个人主页 : 个人主页 个人专栏 : 《数据结构》 《C语言》《C++》《算法》 本篇文章仅是作为小白的我的一些理解,,如果有错误的地方,希望大佬们指出。 题目链接: 34. 在排序数组中查找元素的第一个和最后一个位置 本题数组元素不唯一,可能存在多个target,我们就是

    2024年02月08日
    浏览(48)
  • 34. 在排序数组中查找元素的第一个和最后一个位置(二分查找)

    二分查找到目标值然后左右找到坐标 问题在于:找左右坐标的时候时间复杂度不是 O(logN) 之前提到过二分查找不仅可找到相等的数值,更关键的是 它可以将数组分为截然不同的两种情况 ,因此我们可以借助这个性质找到 第一个大于等于 target 的值(左下标) 和 第一个大于

    2024年01月22日
    浏览(52)
  • 二分查找实例1(在排序数组中查找元素的第一个和最后一个位置)

    给你一个按照非递减顺序排列的整数数组  nums ,和一个目标值  target 。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值  target ,返回  [-1, -1] 。 你必须设计并实现时间复杂度为  O(log n)  的算法解决此问题。 示例 1: 示例 2: 示例 3: 提示

    2024年02月09日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包