首页 > 编程语言 >代码随想录算法训练营第一天 | 704. 二分查找 27. 移除元素

代码随想录算法训练营第一天 | 704. 二分查找 27. 移除元素

时间:2024-06-06 18:11:38浏览次数:33  
标签:27 val nums 元素 随想录 fast slow 数组 移除

704.二分查找
题目:给定一个 n 个元素有序的(升序)整型数组和一个目标值 target,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
提示:
1.你可以假设nums中的所有元素是不重复的。
2.n将在[1,10000]之间。
3.nums的每个元素都将在[-9999,9999]之间。

解题:
思路:二分法可以使用的前提是:1.有序数组;2.数组中无重复元素。
在二分查找过程中,保持不变量,就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作,这就是循环不变量规则。
关键:边界条件,有两种:

一、左闭右闭[left,right]

  1. right=len(nums)-1
  2. while(left<=right),区间有效所以有=
  3. 先写>再写<:
  4. if(nums[middle]>target),target在[left,right]的左区间[left,middle-1],所以调整right=middle-1
  5. if(nums[middle]<target),[left=middle+1,right]

二、左闭右开[left,right)

  1. right=len(nums),定义target在的区间[left,right)
  2. while(left<right)
  3. if(nums[middle]>target):target在[left,middle),right=middle
  4. if(nums[middle]<target):target在[middle+1,right),left=middle+1

27.移除元素
题目:给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不等于 val 的元素数量为 k,要通过此题,您需要执行以下操作:

  • 更改 nums 数组,使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
  • 返回 k。

解题:
思路:数组的元素在内存地址中是连续的,不能单独删除数组中的某个元素,只能覆盖。

一、暴力解法
第一个while循环:遍历数组元素,找到要删除的元素后;
第二个for循环:更新数组,将该元素后面的数前移来覆盖,实现删除。

  1. if找到该节点,将后面的元素向前平移:for j in range(i+1, l):nums[j-1]=nums[j],平移完后l-=1
  2. 不是等于val的节点,i+=1

二、双指针法(快慢指针法)
快指针:寻找新数组的元素 ,新数组就是不含有目标元素的数组
慢指针:指向更新 新数组下标的位置

  1. 只用一个循环fast寻找不等于val的元素
  2. nums[slow]看作一个创建的新数组
  3. while fast<size,没有=,防止fast+=1后超出范围
  4. 不用else,无论是否等于val,fast都要+1

代码随想录的写法:

点击查看代码
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        # 快慢指针
        fast = 0  # 快指针
        slow = 0  # 慢指针
        size = len(nums)
        while fast < size:  # 不加等于是因为,a = size 时,nums[a] 会越界
            # slow 用来收集不等于 val 的值,如果 fast 对应值不等于 val,则把它与 slow 替换
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        return slow

chatgpt的写法更清晰:

点击查看代码
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        slow=0
        for fast in range(len(nums)):
            if nums[fast]!=val:
                nums[slow]=nums[fast]
                slow+=1
        return slow
  1. 使用while需要手动fast+1,使用for就不需要。
  2. 想查看新数组长度,返回slow;想查看新数组,返回nums[:slow]

标签:27,val,nums,元素,随想录,fast,slow,数组,移除
From: https://www.cnblogs.com/MengyiSun/p/18235767

相关文章

  • 面向互联世界的AGFA027R24C2I2V、AGFA027R24C3E4X、AGFA027R24C2E3V、AGFA027R24C3I3V
    Agilex™FPGA产品组合包含一系列产品,可充分满足每一个技术领域(从边缘到嵌入式系统,再到通信和数据中心)的众多可编辑逻辑需求。在所有这些领域中,数据爆炸导致新产品需求激增,以便移动、处理和存储数据并从中获得可执行的深度分析。这些产品的开发人员需要硬件灵活性来应对不断变化......
  • 代码随想录算法训练营第二十八天 | 93.复原IP地址
    93.复原IP地址题目链接文章讲解视频讲解classSolution{private:vector<string>ip;vector<string>result;public:vector<string>restoreIpAddresses(strings){backtracking(s,0);returnresult;}voidbacktrackin......
  • 文心一言 VS 讯飞星火 VS chatgpt (275)-- 算法导论20.3 2题
    二、修改vEB树以支持带有卫星数据的关键字。如果要写代码,请用go语言。文心一言:vEB树(vanEmdeBoas树)是一种用于处理稀疏位集合的高效数据结构,它允许在常数时间内执行查找、插入、删除和前驱/后继操作。然而,标准的vEB树并不直接支持带有卫星数据的关键字。要支持带有......
  • P2716 和谐的雪花
    这道题P2716和谐的雪花本质和P2216[HAOI2007]理想的正方形是一模一样的,评蓝有点高了。本题解解法为单调对列。当然,看题目,是可以使用ST表或者线段树之类的做。中心思想就是用单调队列维护固定区间内最大最小值,加上二分答案。根据题意,很容易想象到二分\(n\)的取值,剩下......
  • 27、matlab傅里叶变换:fft()函数
    1、fft 快速傅里叶变换语法Y=fft(X)使用快速傅里叶变换(FFT)算法计算X的离散傅里叶变换(DFT)。Y=fft(X,n)返回n点DFT。Y=fft(X,n,dim)返回沿维度dim的傅里叶变换。例如,如果X是矩阵,则fft(X,n,2)返回每行的n点傅里叶变换含噪信号1)原始信号加噪声......
  • 2024年6月 AWVS -24.4.27详细安装教程附下载教程含windows和linux多版本
    免责声明请勿利用文章内的相关技术从事非法测试。由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失,均由使用者本人负责,作者不为此承担任何责任,请务必遵守网络安全法律法规。本文仅用于测试,请完成测试后24小时删除,请勿用于商业用途。如文中内容涉及侵权......
  • 代码随想录算法训练营第一天| 704. 二分查找、27. 移除元素(数组)
    第一次打卡,记录还不够充分,会慢慢丰富起来一、二分查找题目链接:704.二分查找-力扣(LeetCode)讲解链接:Carl讲解视频讲解:代码随想录讲解 情况1:左闭右闭区间情况2:左闭右开区间 二、移除元素题目链接:27.移除元素-力扣(LeetCode)讲解链接:Carl讲解视频讲解:代码随想......
  • 代码随想录算法训练营第一天 | 704. 二分查找,27. 移除元素
    题目链接:704.二分查找思路:该题为有序数组查找,采用二分法。根据区间分为左闭右闭和左闭右开两种情况坑:左右区间的开闭补充:vector容器时间复杂度:O(logn)空间复杂度:O(1)题目链接:27.移除元素思路:题目说返回k个元素之后留下什么不重要,也不考虑数组剩下元素的......
  • 【语音处理】声音信号频谱分析仪(时域分析 频域分析)【含GUI Matlab源码 4627期】
    ✅博主简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,Matlab项目合作可私信。......
  • 代码随想录 数组总结
    数组总结主要包括二分法双指针滑动窗口模拟 二分法 循环不变量原则拓展考虑学习浮点数二分整数二分扩展题目双指针 快慢指针 原地解决问题、双向解决问题 滑动窗口滑动窗口的精妙之处在于根据当前子序列和大小的情况,不断调节子序列的起始位置。从而将O(n^2)......