【蓝桥杯入门到入土】最基础的数组你真的掌握了吗?
文章目录
- 一:数组理论基础
- 二:数组知识点总结
- 三:数组这种数据结构的优点和缺点是什么?
- 四:实战解题
- 1. 移除元素
- 暴力解法
- 双指针法
- 2.有序数组的平方
- 暴力解法
- 双指针法
- 最后说一句
一:数组理论基础
首先要知道数组在内存中的存储方式,这样才能真正理解数组相关的题
数组是存放在连续内存空间上的相同类型数据的集合。
数组可以方便的通过下标索引的方式获取到下标下对应的数据。
举一个字符数组的例子,如图所示:
需要两点注意的是
- 数组下标都是从0开始的。
- 数组内存空间的地址是连续的
正是因为数组的在内存空间的地址是连续的,所以我们在删除或者增添元素的时候,就难免要移动其他元素的地址。
例如删除下标为3的元素,需要对下标为3的元素后面的所有元素都要做移动操作,如图所示:
二:数组知识点总结
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;}
}
最后说一句
感谢大家的阅读,文章通过网络资源与自己的学习过程整理出来,希望能帮助到大家。
才疏学浅,难免会有纰漏,如果你发现了错误的地方,可以提出来,我会对其加以修改。
相关文章:

【蓝桥杯入门到入土】最基础的数组你真的掌握了吗?
文章目录一:数组理论基础二:数组知识点总结三:数组这种数据结构的优点和缺点是什么?四:实战解题1. 移除元素暴力解法双指针法2.有序数组的平方暴力解法双指针法最后说一句一:数组理论基础 首先要知道数组在…...
Java Set系列集合(Collections集合工具类、可变参数)
目录Set系列集系概述HashSet集合元素无序的底层原理:哈希表HashSet集合元素去重复的底层原理LinkedHashSet有序实现原理TreeSetCollection集合总结可变参数Collections集合工具类Set系列集系概述 Set系列集合特点 无序:存取顺序不一致不重复࿱…...
chromium构建原生AS项目-记录1
构建的chromium版本:待补充重要说明:so文件加载的过程文件:base_java.jar包文件路径:org.chromium.base.library_loader.LibraryLoader方法:loadAlreadyLocked(Context context)line166 :Native…...

Mybatis-Plus 开发提速器:mybatis-plus-generator-ui
Mybatis-Plus 开发提速器:mybatis-plus-generator-ui 1.简介 github地址 : https://github.com/davidfantasy/mybatis-plus-generator-ui 提供交互式的Web UI用于生成兼容mybatis-plus框架的相关功能代码,包括Entity,Mapper,Mapper.xml,Se…...
李迟2023年02月工作生活总结
本文为 2023 年 2 月工作生活总结。 研发编码 Linux Go 某工程使用到一些数据的统计,为方便,使用 map 存储数量,由于其是无序的,输出的列表顺序不固定,将其和历史版本对比不方便,所以需要将 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,一起来快乐地糟蹋服务器!”
写作前面 工具永远只是为了帮助自己提升工作效率 —— 沃兹基硕得 所以说,为什么要使用jupyterlab呢?当然是因为基于服务器来处理数据就可以使劲造了,而且深切地感觉到,“R这玩意儿是人用的吗”。 jupyter-lab | mamba安装以及…...

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

【UE4 】制作螺旋桨飞机
一、素材资源链接:https://pan.baidu.com/s/1xPVYYw05WQ6FABq_ZxFifg提取码:ivv8二、课程视频链接https://www.bilibili.com/video/BV1Bb411h7qw/?spm_id_from333.337.search-card.all.click&vd_source36a3e35639c44bb339f59760641390a8三、最终效果…...
五.家庭:亲情背后有理性
5.1经济学帝国主义【单选题】以下属于经济学研究范围的是( )。A、约束最优化B、稀缺资源配置C、价格竞争与非价格竞争D、以上都对我的答案:D【多选题】为何有学科分类?A、分工B、专业化C、累积创新D、科技进步我的答案:ABCD【判断…...

【Leedcode】栈和队列必备的面试题(第三期)
【Leedcode】栈和队列必备的面试题(第三期) 文章目录【Leedcode】栈和队列必备的面试题(第三期)一、题目(用两个栈实现队列)二、思路图解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 之前的假设: Raw input graph computational graph,即原始图等于计算…...

【Node.js算法题】数组去重、数组删除元素、数组排序、字符串排序、字符串反向、字符串改大写 、数组改大写、字符替换
文章目录前言数组去重数组删除元素数组排序字符串排序字符串反向字符串改大写数组改大写字符替换字符替换运行结果: 总结前言 本期文章是js的一些算法题,包括…...

Win10系统开始菜单无法点击解决方法分享
Win10系统开始菜单无法点击解决方法分享。有用户电脑一开机之后,就出现了开始菜单无法正常点击的情况。我们很多设置项都是通过开始菜单来进行开启的。那么这个功能无法点击了怎么办呢?接下来我们一起来看看以下的解决方法分享吧。 方法一: 1…...
libmodbus从linux访问window上的服务超时问题
window:使用EasyModbusTCP Server Simulator 作为服务。linux:程序:#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)——双线性插值
双线性插值是一种常用的图像插值方法,用于将低分辨率的图像放大到高分辨率。它基于一个假设:在两个相邻像素之间的值是线性的。 双线性插值考察444邻域的像素点,并根据距离设置权值。虽然计算量增大使得处理时间变长,但是可以有效…...
NXP iMX8系列处理器Pin Multiplexing定义说明
By Toradex秦海1). 简介为了提高处理器的设计灵活性和可用性,NXP的所有i.MX系列处理器都配备了基于 IOMUX Controller (IOMUXC)和IOMUX来使能Pin Mux功能,使得一个特定的IO管脚可以选择不同的可能多达8种的功能定义模块(ALT0, ALT1, ALT2, ALT3...)&…...

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

Centos和Window系统下Frp内网穿透
frp 是一个高性能的内网穿透的反向代理软件,支持 TCP、UDP、HTTP、HTTPS 等常见协议(TCP最常用),可以将处于局域网或者家用电脑主机、办公电脑主机通过中转服务器的方式暴露在公网里,使用户可以通过访问公网的IP(域名)…...
春招冲刺(四):flex布局面试题总结
flex布局面试题总结 Q1:什么是弹性盒布局? 特点:让元素对不同屏幕尺寸和不同显示设备做好适应。在响应式网站表现较好。 一、容器属性 Q2:display:flex和display:inline-flex的作用 使容器变成弹性布局,为其子元素…...

UE5 学习系列(二)用户操作界面及介绍
这篇博客是 UE5 学习系列博客的第二篇,在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下: 【Note】:如果你已经完成安装等操作,可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作,重…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...
k8s从入门到放弃之Ingress七层负载
k8s从入门到放弃之Ingress七层负载 在Kubernetes(简称K8s)中,Ingress是一个API对象,它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress,你可…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建
制造业采购供应链管理是企业运营的核心环节,供应链协同管理在供应链上下游企业之间建立紧密的合作关系,通过信息共享、资源整合、业务协同等方式,实现供应链的全面管理和优化,提高供应链的效率和透明度,降低供应链的成…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...

聊聊 Pulsar:Producer 源码解析
一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台,以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中,Producer(生产者) 是连接客户端应用与消息队列的第一步。生产者…...
反射获取方法和属性
Java反射获取方法 在Java中,反射(Reflection)是一种强大的机制,允许程序在运行时访问和操作类的内部属性和方法。通过反射,可以动态地创建对象、调用方法、改变属性值,这在很多Java框架中如Spring和Hiberna…...
MySQL中【正则表达式】用法
MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现(两者等价),用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例: 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...
OpenLayers 分屏对比(地图联动)
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能,和卷帘图层不一样的是,分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...