当前位置: 首页 > 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;为其子元素…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...

STM32HAL库USART源代码解析及应用

STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...

Linux系统部署KES

1、安装准备 1.版本说明V008R006C009B0014 V008&#xff1a;是version产品的大版本。 R006&#xff1a;是release产品特性版本。 C009&#xff1a;是通用版 B0014&#xff1a;是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存&#xff1a;1GB 以上 硬盘&#xf…...