当前位置: 首页 > news >正文

【蓝桥杯入门到入土】最基础的数组你真的掌握了吗?

文章目录

  • 一:数组理论基础
  • 二:数组知识点总结
  • 三:数组这种数据结构的优点和缺点是什么?
  • 四:实战解题
    • 1. 移除元素
      • 暴力解法
      • 双指针法
    • 2.有序数组的平方
      • 暴力解法
      • 双指针法
    • 最后说一句

一:数组理论基础

首先要知道数组在内存中的存储方式,这样才能真正理解数组相关的题

数组是存放在连续内存空间上的相同类型数据的集合。

数组可以方便的通过下标索引的方式获取到下标下对应的数据。

举一个字符数组的例子,如图所示:

image-20230301103359412

需要两点注意的是

  • 数组下标都是从0开始的。
  • 数组内存空间的地址是连续的

正是因为数组的在内存空间的地址是连续的,所以我们在删除或者增添元素的时候,就难免要移动其他元素的地址。

例如删除下标为3的元素,需要对下标为3的元素后面的所有元素都要做移动操作,如图所示:

image-20230301103422604

二:数组知识点总结

在这里插入图片描述

1、数组当中可以存储“基本数据类型”的数据,也可以存储“引用数据类型”的数据。

2、数组因为是引用类型,所以数组对象存储在 堆内存 当中。(数组是存储在堆当中的)

3、数组当中如果存储的是“java对象”的话,实际上存储的是对象的“引用(内存地址)”,数组中不能直接存储java对象。

4、所有的数组对象都有 length 属性(java自带的),用来获取数组中元素的个数。

5、java中的数组要求数组中元素的 类型统一。

比如:int类型数组只能存储int类型,Person类型数组只能存储Person类型。

6、数组在内存方面存储的时候,数组中的元素内存地址(存储的每一个元素都是有规则的挨着排列的)是连续的。内存地址连续。(数组特点)

7、所有的数组都是拿“第一个小方框的内存地址”作为整个数组对象的内存地址。
(数组中首元素的内存地址作为整个数组对象的内存地址。)

8、数组中每一个元素都是有下标的,下标从0开始,以1递增。最后一个元素的下标是:length - 1

三:数组这种数据结构的优点和缺点是什么?

在这里插入图片描述

优点:查询/查找/检索某个下标上的元素时效率极高。
原因:

第一:每一个元素的内存地址在空间存储上是连续的。

第二:每一个元素类型相同,所以占用空间大小一样。

第三:知道第一个元素内存地址,知道每一个元素占用空间的大小,又知道下标,所以通过一个数学表达式就可以计算出某个下标上元素的内存地址。直接通过内存地址定位元素,所以数组的检索效率是最高的。
注意:

缺点:
第一:由于为了保证数组中每个元素的内存地址连续,所以在数组上随机删除或者增加元素的时候,效率较低,因为随机增删元素会涉及到后面元素统一向前或者向后位移的操作。
第二:数组不能存储大数据量。
因为很难在内存空间上找到一块特别大的连续的内存空间。
注意:
对于数组中最后一个元素的增删,是没有效率影响的。

四:实战解题

1. 移除元素

力扣链接

给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。

不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 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],也会被视作正确答案。

暴力解法

这个题目暴力的解法就是两层for循环,一个for循环遍历数组元素 ,第二个for循环更新数组。

很明显暴力解法的时间复杂度是O(n^2),这道题目暴力解法在leetcode上是可以过的。

代码如下:

class Solution {
public:int removeElement(vector<int>& nums, int val) {int size = nums.size();for (int i = 0; i < size; i++) {if (nums[i] == val) { // 发现需要移除的元素,就将数组集体向前移动一位for (int j = i + 1; j < size; j++) {nums[j - 1] = nums[j];}i--; // 因为下标i以后的数值都向前移动了一位,所以i也向前移动一位size--; // 此时数组的大小-1}}return size;}
};
  • 时间复杂度:O(n^2)
  • 空间复杂度:O(1)

双指针法

思路及算法
由于题目要求删除数组中等于val的元素,因此输出数组的长度一定小于等于输入数组的长度,我们可以把输出的数组直接写在输入数组上。可以使用双指针:右指针right指向当前将要处理的元素,左指针left指向下一个将要赋值的位置。

·如果右指针指向的元素不等于val,它一定是输出数组的一个元素,我们就将右指针指向的元素复制到左指针位置,然后将左右指针同时右移;

·如果右指针指向的元素等于val,它不能在输出数组里,此时左指针不动,右指针右移一位。

整个过程保持不变的性质是:区间[0, left)中的元素都不等于value。当左右指针遍历完输入数组以后,left的值就是输出数组的长度。
这样的算法在最坏情况下(输入数组中没有元素等于value),左右指针各遍历了数组一次。

class Solution {public int removeElement(int[] nums, int val) {// 快慢指针int slowIndex = 0;for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {if (nums[fastIndex] != val) {nums[slowIndex] = nums[fastIndex];slowIndex++;}}return slowIndex;}
}

在这里插入图片描述

2.有序数组的平方

力扣链接

给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。

示例 1:

输入:nums = [-4,-1,0,3,10] 输出:[0,1,9,16,100] 解释:平方后,数组变为 [16,1,0,9,100],排序后,数组变为 [0,1,9,16,100]

示例 2:

输入:nums = [-7,-3,2,3,11] 输出:[4,9,9,49,121]

在这里插入图片描述

暴力解法

最直观的想法,莫过于:每个数平方之后,排个序,美滋滋,代码如下:

class Solution {
public:vector<int> sortedSquares(vector<int>& A) {for (int i = 0; i < A.size(); i++) {A[i] *= A[i];}sort(A.begin(), A.end()); // 快速排序return A;}
};

这个时间复杂度是 O(n + nlogn), 可以说是O(nlogn)的时间复杂度,但为了和下面双指针法算法时间复杂度有鲜明对比,我记为 O(n + nlog n)。

双指针法

数组其实是有序的, 只不过负数平方之后可能成为最大数了。

那么数组平方的最大值就在数组的两端,不是最左边就是最右边,不可能是中间。

此时可以考虑双指针法了,i指向起始位置,j指向终止位置。

定义一个新数组result,和A数组一样的大小,让k指向result数组终止位置。

class Solution {public int[] sortedSquares(int[] nums) {int right = nums.length - 1;int left = 0;int[] result = new int[nums.length];int index = result.length - 1;while (left <= right) {if (nums[left] * nums[left] > nums[right] * nums[right]) {// 正数的相对位置是不变的, 需要调整的是负数平方后的相对位置result[index--] = nums[left] * nums[left];++left;} else {result[index--] = nums[right] * nums[right];--right;}}return result;}
}

最后说一句

感谢大家的阅读,文章通过网络资源与自己的学习过程整理出来,希望能帮助到大家。

才疏学浅,难免会有纰漏,如果你发现了错误的地方,可以提出来,我会对其加以修改。

在这里插入图片描述

相关文章:

【蓝桥杯入门到入土】最基础的数组你真的掌握了吗?

文章目录一&#xff1a;数组理论基础二&#xff1a;数组知识点总结三&#xff1a;数组这种数据结构的优点和缺点是什么&#xff1f;四&#xff1a;实战解题1. 移除元素暴力解法双指针法2.有序数组的平方暴力解法双指针法最后说一句一&#xff1a;数组理论基础 首先要知道数组在…...

Java Set系列集合(Collections集合工具类、可变参数)

目录Set系列集系概述HashSet集合元素无序的底层原理&#xff1a;哈希表HashSet集合元素去重复的底层原理LinkedHashSet有序实现原理TreeSetCollection集合总结可变参数Collections集合工具类Set系列集系概述 Set系列集合特点 无序&#xff1a;存取顺序不一致不重复&#xff1…...

chromium构建原生AS项目-记录1

构建的chromium版本&#xff1a;待补充重要说明&#xff1a;so文件加载的过程文件&#xff1a;base_java.jar包文件路径&#xff1a;org.chromium.base.library_loader.LibraryLoader方法&#xff1a;loadAlreadyLocked&#xff08;Context context&#xff09;line166 :Native…...

Mybatis-Plus 开发提速器:mybatis-plus-generator-ui

Mybatis-Plus 开发提速器&#xff1a;mybatis-plus-generator-ui 1.简介 github地址 &#xff1a; https://github.com/davidfantasy/mybatis-plus-generator-ui 提供交互式的Web UI用于生成兼容mybatis-plus框架的相关功能代码&#xff0c;包括Entity,Mapper,Mapper.xml,Se…...

李迟2023年02月工作生活总结

本文为 2023 年 2 月工作生活总结。 研发编码 Linux Go 某工程使用到一些数据的统计&#xff0c;为方便&#xff0c;使用 map 存储数量&#xff0c;由于其是无序的&#xff0c;输出的列表顺序不固定&#xff0c;将其和历史版本对比不方便&#xff0c;所以需要将 key 排序再输…...

【Python百日进阶-Web开发-Vue3】Day542 - Vue3 商城后台 02:Windi CSS 与 Vue Router4

文章目录 一、WindiCSS 初始1.1 WindiCSS 是什么?1.2 为什么选择 Windi CSS?1.3. 基础用法1.4 集成二、简单按钮2.1 设置背景色2.2 设置字体颜色和上下左右padding2.3 设置圆角2.4 鼠标悬浮,颜色加深2.5 鼠标划入动画2.6 设置阴影2.7 @apply 抽离class代码到 style 块中三、…...

Jupyter Lab | “丢下R,一起来快乐地糟蹋服务器!”

写作前面 工具永远只是为了帮助自己提升工作效率 —— 沃兹基硕得 所以说&#xff0c;为什么要使用jupyterlab呢&#xff1f;当然是因为基于服务器来处理数据就可以使劲造了&#xff0c;而且深切地感觉到&#xff0c;“R这玩意儿是人用的吗”。 jupyter-lab | mamba安装以及…...

分页与分段

前面我们分析了虚拟地址和物理地址 我们这里进行一个简单的分析 这个是程序运行时的地址映射 那么这些碎片&#xff0c;我们现在的操作系统究竟如何处理呢&#xff1f; 我们再引入一个实际问题 我们如何把右边的进程p塞入左边的内存空间里面 有一种方法将p5kill掉&#xff…...

【UE4 】制作螺旋桨飞机

一、素材资源链接&#xff1a;https://pan.baidu.com/s/1xPVYYw05WQ6FABq_ZxFifg提取码&#xff1a;ivv8二、课程视频链接https://www.bilibili.com/video/BV1Bb411h7qw/?spm_id_from333.337.search-card.all.click&vd_source36a3e35639c44bb339f59760641390a8三、最终效果…...

五.家庭:亲情背后有理性

5.1经济学帝国主义【单选题】以下属于经济学研究范围的是&#xff08; &#xff09;。A、约束最优化B、稀缺资源配置C、价格竞争与非价格竞争D、以上都对我的答案&#xff1a;D【多选题】为何有学科分类?A、分工B、专业化C、累积创新D、科技进步我的答案&#xff1a;ABCD【判断…...

【Leedcode】栈和队列必备的面试题(第三期)

【Leedcode】栈和队列必备的面试题&#xff08;第三期&#xff09; 文章目录【Leedcode】栈和队列必备的面试题&#xff08;第三期&#xff09;一、题目&#xff08;用两个栈实现队列&#xff09;二、思路图解1.定义两个栈2.初始化两个数组栈3. 将数据放入pushST数组栈中4.删除…...

《图机器学习》-GNN Augmentation and Training

GNN Augmentation and Training一、Graph Augmentation for GNNs1、Feature Augmentation2、Structure augmentation3、Node Neighborhood Sampling一、Graph Augmentation for GNNs 之前的假设&#xff1a; Raw input graph computational graph&#xff0c;即原始图等于计算…...

【Node.js算法题】数组去重、数组删除元素、数组排序、字符串排序、字符串反向、字符串改大写 、数组改大写、字符替换

文章目录前言数组去重数组删除元素数组排序字符串排序字符串反向字符串改大写数组改大写字符替换字符替换运行结果&#xff1a; ![在这里插入图片描述](https://img-blog.csdnimg.cn/8ac1c15e6f0944cdb8ca50bcb844182a.png)总结前言 本期文章是js的一些算法题&#xff0c;包括…...

Win10系统开始菜单无法点击解决方法分享

Win10系统开始菜单无法点击解决方法分享。有用户电脑一开机之后&#xff0c;就出现了开始菜单无法正常点击的情况。我们很多设置项都是通过开始菜单来进行开启的。那么这个功能无法点击了怎么办呢&#xff1f;接下来我们一起来看看以下的解决方法分享吧。 方法一&#xff1a; 1…...

libmodbus从linux访问window上的服务超时问题

window&#xff1a;使用EasyModbusTCP Server Simulator 作为服务。linux:程序&#xff1a;#include <stdio.h> #include <modbus/modbus.h>int main() {modbus_t *ctx;uint16_t holding_registers[1];// Create a new Modbus TCP contextctx modbus_new_tcp(&quo…...

挑战图像处理100问(26)——双线性插值

双线性插值是一种常用的图像插值方法&#xff0c;用于将低分辨率的图像放大到高分辨率。它基于一个假设&#xff1a;在两个相邻像素之间的值是线性的。 双线性插值考察444邻域的像素点&#xff0c;并根据距离设置权值。虽然计算量增大使得处理时间变长&#xff0c;但是可以有效…...

NXP iMX8系列处理器Pin Multiplexing定义说明

By Toradex秦海1). 简介为了提高处理器的设计灵活性和可用性&#xff0c;NXP的所有i.MX系列处理器都配备了基于 IOMUX Controller (IOMUXC)和IOMUX来使能Pin Mux功能&#xff0c;使得一个特定的IO管脚可以选择不同的可能多达8种的功能定义模块(ALT0, ALT1, ALT2, ALT3...)&…...

用Python的Supervisor進行進程監控以及自動啓動

python 限制同一时间只执行一个 作服務器端開發的同窗應該都對進程監控不會陌生&#xff0c;最近剛好要更換 uwsgi 爲 gunicorn&#xff0c;而gunicorn又剛好有這麼一章講進程監控&#xff0c;因此多研究了下。python 結合以前在騰訊工做的經驗&#xff0c;也會講講騰訊的服務…...

Centos和Window系统下Frp内网穿透

frp 是一个高性能的内网穿透的反向代理软件&#xff0c;支持 TCP、UDP、HTTP、HTTPS 等常见协议(TCP最常用)&#xff0c;可以将处于局域网或者家用电脑主机、办公电脑主机通过中转服务器的方式暴露在公网里&#xff0c;使用户可以通过访问公网的IP&#xff08;域名&#xff09;…...

春招冲刺(四):flex布局面试题总结

flex布局面试题总结 Q1&#xff1a;什么是弹性盒布局&#xff1f; 特点&#xff1a;让元素对不同屏幕尺寸和不同显示设备做好适应。在响应式网站表现较好。 一、容器属性 Q2&#xff1a;display:flex和display:inline-flex的作用 使容器变成弹性布局&#xff0c;为其子元素…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...