leetcode 面试经典 150 题:移除元素

server/2024/12/16 17:51:46/
链接移除元素
题序号27
类型数组
解题方法双指针
难度简单

题目

给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k,要通过此题,您需要执行以下操作:

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

  • 用户评测
    评测机将使用以下代码测试您的解决方案:
    int[] nums = […]; // 输入数组
    int val = …; // 要移除的值
    int[] expectedNums = […]; // 长度正确的预期答案。 // 它以不等于 val 的值排序。
    int k = removeElement(nums, val); // 调用你的实现
    assert k == expectedNums.length; sort(nums, 0, k); // 排序 nums 的前 k 个元素
    for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
    }
    如果所有的断言都通过,你的解决方案将会 通过。

  • 示例 1
    输入:nums = [3,2,2,3], val = 3 输出:2, nums = [2,2,,]
    解释:你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。 你在返回的 k 个元素之外留下了什么并不重要(因此它们并不计入评测)。

  • 示例 2
    输入:nums = [0,1,2,2,3,0,4,2], val = 2 输出:5, nums = [0,1,4,0,3,,,_]
    解释:你的函数应该返回 k = 5,并且 nums 中的前五个元素为 0,0,1,3,4。 注意这五个元素可以任意顺序返回。 你在返回的 k 个元素之外留下了什么并不重要(因此它们并不计入评测)。

  • 提示
    0 <= nums.length <= 100
    0 <= nums[i] <= 50
    0 <= val <= 100

题解

双指针

  1. 要点:一个指针 right 用于遍历数组,另一个指针 left 用于指向下一个不等于 val 的元素应该放置的位置。
  2. 时间复杂度:O(n);
  3. 空间复杂度:O(1);
  4. c++ 算法:
class Solution {
public:int removeElement(vector<int>& nums, int val) {int n = nums.size();int left = 0;for (int right = 0; right < n; right++) {if (nums[right] != val) {nums[left] = nums[right];left++;}}nums.resize(left); //调整 nums 大小return left;}
};
  1. 演示:以示例1为例
推演:
nums = 3 2 2 3
val = 3removeElement:n = nums.size = 4left = 0for right=0; right<4; right++if nums[0] != 3 //等于3,if不成立for right=1; right<4; right++if nums[1] != 3nums[0] = nums[1] = 2left++ 等于1for right=2; right<4; right++if nums[2] != 3 nums[1] = nums[2] = 2left++ 等于2for right=3; right<4; right++if nums[3] != 3 //等于3,if不成立for right=4; right<4; right++ //for循环不成立,退出nums.resize(left) //调整nums大小为leftreturn left //返回 

c++ 完整demo

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>using namespace std;class Solution {
public:int removeElement(vector<int>& nums, int val) {int n = nums.size();int left = 0;for (int right = 0; right < n; right++) {if (nums[right] != val) {nums[left] = nums[right];left++;}}nums.resize(left); //调整 nums 大小return left;}
};
int main(){vector<int> nums = {3, 2, 2, 3};int val = 3;Solution solution;int number = solution.removeElement(nums, val);assert(number == nums.size());cout << "number: " << number << endl;cout << "nums.size: " << nums.size() << endl;for(int i = 0; i< number; i++){cout << "i: " << i  << ", nums[" << i << "]: "<< nums[i] << endl;}return 0;
}

http://www.ppmy.cn/server/150687.html

相关文章

聊聊Oracle自适应查询优化

成也AQO败也AQO 因为工作的原因&#xff0c;我们接触到的客户大部分是金融和运营商行业&#xff0c;这些客户有个最大的特点是追求稳定&#xff0c;对于使用数据库新特性持保守的态度&#xff0c;不会轻易尝试某些可能会导致生产系统不稳定的新特性。上线前通常都会将一些新特…

SpringBoot【十】mybatis之xml映射文件>、<=等特殊符号写法!

一、前言&#x1f525; 环境说明&#xff1a;Windows10 Idea2021.3.2 Jdk1.8 SpringBoot 2.3.1.RELEASE 在利用mybatis进行开发的时候&#xff0c;编写sql时可能少不了>、<等比较符号&#xff0c;但是在mapper映射文件中直接使用是不行的&#xff0c;会报错&#xff0…

Guava库 学习入门--概览与入门

Guava库的介绍 Guava库是由Google开发的Java开源库&#xff0c;它的主要目的是简化常见的编程任务&#xff0c;提供高效的数据处理方法。Guava库中的功能覆盖了从集合操作、缓存、函数式编程、并发编程以及其他诸多实用的工具类。 Guava的安装与依赖配置 Guava库可以通过Mav…

使用Docker部署FTP和Nginx并通过HTTP访问FTP里的文件

使用 Docker 部署 FTP 和 Nginx 通过 HTTP 访问 FTP 里的文件&#xff0c;这是一个常见的需求&#xff0c;通常用于将存储在 FTP 服务器上的文件通过 Web 方式提供访问。以下是如何操作的详细步骤&#xff1a; 1. 部署 FTP 服务器 (vsftpd) 我们使用 fauria/vsftpd 镜像&…

修复代码漏洞的具体案例(C++/HTML/PHP/SQL/JavaScript)

以下是一些修复代码漏洞的具体案例&#xff1a; 案例一&#xff1a;SQL 注入漏洞修复&#xff08;Web 应用程序&#xff09; 漏洞描述 假设一个简单的用户登录功能的 PHP 代码存在 SQL 注入漏洞。代码可能类似于以下部分&#xff1a; php $username $_POST[username];$pass…

AIGC 014-ConsisID通过频率解耦将角色信息注入到文生视频模型

AIGC 014-ConsisID通过频率解耦将角色信息注入到文生视频模型 文章目录 0 论文工作1 论文方法2 实验结果 0 论文工作 身份保持的文本到视频生成是视频生成领域一个极具挑战性的任务&#xff0c;其目标是创建与给定文本描述相符且具有一致身份的视频。作者提出了一种名为 Consi…

PyQt事件机制练习

一、思维导图 二、代码 import sysfrom PyQt6.QtTextToSpeech import QTextToSpeech from PyQt6.QtWidgets import QApplication, QWidget, QLabel, QPushButton, QLineEdit from PyQt6 import uic from PyQt6.QtCore import Qt, QTimerEvent, QTimeclass MyWidget(QWidget):d…

Docker的镜像

目录 1. 镜像是什么&#xff1f;&#xff1f;2. 镜像命令详解2.1 镜像命令清单2.2 docker rmi命令2.3 docker save命令2.4 docker load命令2.5 docker history命令2.6 docker import命令2.7 docker image prune命令2.8 docker build命令 3. 镜像的操作4. 离线迁移镜像5. 镜像存…