【面试经典150 | 数组】移除元素

这篇具有很好参考价值的文章主要介绍了【面试经典150 | 数组】移除元素。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

写在前面

本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更……

专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行回顾与总结,文章结构大致如下,部分内容会有增删:

  • Tag:介绍本题牵涉到的知识点、数据结构;
  • 题目来源:贴上题目的链接,方便大家查找题目并完成练习;
  • 题目解读:复述题目(确保自己真的理解题目意思),并强调一些题目重点信息;
  • 解题思路:介绍一些解题思路,每种解题思路包括思路讲解、实现代码以及复杂度分析;
  • 知识回忆:针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【原地操作】【双指针】【数组】


题目来源

面试经典 150 题 —— 27. 移除元素

【面试经典150 | 数组】移除元素,面试经典150题,原地操作,双指针,数组,c++,算法

题目解读

移除数组 nums 中的 val 值,要求原地操作,但是数组中的元素顺序可以改变,最后输出移除所有 val 后数组的长度。


解题思路

方法一:原地操作

原地操作,那么我们就不能使用额外的数组来存放非 val 的元素从而实现移除操作,但是我们可以使用 “覆盖” 的思想来模拟移除操作。

具体地,维护两个指针 iji 指针用来遍历数组查找哪个位置上的元素等于 valj 指向用来覆盖 i 位置的元素。初始化 i = 0j = nums.size() - 1,只要 nums[i] = val,我们就用 nums[j] 来覆盖,使用了 nums[j] 之后,j 指针就要左移指向下一个将要使用的元素;只有 nums[i] != val 时,我们才会右移 i 指针,准备处理下一个元素。

直到 i 指针超过 j 指针,表明可以被用来覆盖的元素已经没有了,i 的值就是原数组中的非 val 的数,直接返回 i

实现代码

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int i = 0, j = nums.size() - 1;
        while (i <= j) {
            if (nums[i] == val) {
                nums[i] = nums[j--];
            }
            else ++i;
        }
        return i;
    }
};

复杂度分析

时间复杂度: O ( n ) O(n) O(n) n n n 为原数组 nums 的长度。

空间复杂度: O ( 1 ) O(1) O(1),仅使用了两个指针变量,是原地操作。


写在最后

如果文章内容有任何错误或者您对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法,欢迎评论区交流。

最后,感谢您的阅读,如果感到有所收获的话可以给博主点一个 👍 哦。文章来源地址https://www.toymoban.com/news/detail-706371.html

到了这里,关于【面试经典150 | 数组】移除元素的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【面试经典150 | 双指针】两数之和

    本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更…… 专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行回顾与总结,文章结构大致如下,部分内容会有增删: Tag:介绍本题牵涉到的知识点、数据结构; 题目来源:

    2024年02月09日
    浏览(36)
  • 【C/C++练习】经典的快慢指针问题---移除元素

    题目出处 :移除元素  对于本题我将按照由易到难的顺序为大家分享三种解题思路,并逐一分析它们的优劣,以及注意事项。  我想暴力求解应该是第一次接触到此题的小伙伴们最先想出来的办法吧。这道题目暴力求解就是去遍历数组,当遇到数组元素等于 val 的时候,将

    2024年02月11日
    浏览(89)
  • 【面试经典150 | 数组】合并两个有序数组

    本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更…… 专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行回顾与总结,文章结构大致如下,部分内容会有增删: Tag:介绍本题牵涉到的知识点、数据结构; 题目来源:

    2024年02月09日
    浏览(46)
  • 【面试经典150 | 哈希表】存在重复元素 II

    【哈希表】【滑动窗口】【数组】 219. 存在重复元素 II 判断在数组中有没有相同的元素小于一定的距离。 我们维护一个哈希表来记录数组中的元素以及上一次出现的位置,如果上一次出现的位置和这一次出现的位置之差小于等于 k ,那就返回 true ,否则返回 false 。 实现代码

    2024年02月07日
    浏览(34)
  • 1.5 面试经典150题 - 轮转数组

    轮转数组 给定一个整数数组  nums ,将数组中的元素向右轮转  k   个位置,其中  k   是非负数。 注意:本题需要原地操作 本题解题思路是: 以[]1, 2, 3, 4, 5, 6, 7] 3 为例 1. 先整体轮转,将 [1, 2, 3, 4, 5, 6, 7]转为 [7, 6, 5, 4, 3, 2, 1] 2. 再局部分别轮转前k个和剩余的,[5, 6, 7,   

    2024年01月16日
    浏览(38)
  • 面试经典150题:数组/字符串合集

    新专栏,预计两个月写完吧,每天下班回来抽空做几道题。会把做题计划顺序记录下来,如果你有缘,刷到这个开篇序列,那就跟着文章去练题吧。初学者可以慢慢来 88. 合并两个有序数组 27. 移除元素 这是前后指针覆盖做的,也可以双向指针交换做,思路 i从0开始,j从尾

    2024年02月08日
    浏览(43)
  • 【面试经典 150 | 数组】最后一个单词的长度

    本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更…… 专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行回顾与总结,文章结构大致如下,部分内容会有增删: Tag:介绍本题牵涉到的知识点、数据结构; 题目来源:

    2024年04月22日
    浏览(59)
  • LeetCode150道面试经典题-- 存在重复元素 II(简单)

    给你一个整数数组  nums 和一个整数  k ,判断数组中是否存在两个 不同的索引   i  和   j ,满足 nums[i] == nums[j] 且 abs(i - j) = k 。如果存在,返回 true ;否则,返回 false 。 示例 1:   输入:nums = [1,2,3,1], k = 3 输出:true 示例 2:   输入:nums = [1,0,1,1], k = 1 输出:true  示例

    2024年02月12日
    浏览(46)
  • 1.1 面试经典 150 题-合并两个有序数组

    合并两个有序数组

    2024年01月16日
    浏览(51)
  • 【leetcode刷题之路】面试经典150题(2)——双指针+滑动窗口+矩阵

    2 双指针 2.1 【双指针】验证回文串 题目地址:https://leetcode.cn/problems/valid-palindrome/description/?envType=study-plan-v2envId=top-interview-150   详见代码。 2.2 【双指针】判断子序列 题目地址:https://leetcode.cn/problems/is-subsequence/description/?envType=study-plan-v2envId=top-interview-150   双指针挨个遍

    2024年02月19日
    浏览(50)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包