代码随想录—数组 | Aryue的个人博客

type

status

date

slug

summary

🤔 综述

😁薛定谔的学习：在你用到一个知识之前，它永远无用。

数组往往是学习算法和数据结构的第一步，因为其相较于其他内容比较简单。但这里为什么说数组也是最不简单的呢？不仅仅是因为数组这部分也有相对比较困难的题目，我认为有以下几个难点：

这部分应该都很熟悉，数组就是在一段连续的内存上排列的一堆相同数据类型的数据。

至于数组插入，数组赋值等都是什么时间复杂度，这里就不说了，因为学过无数次了。

如上图，是Java中二维数组的内存分布。在不同的语言中，情况不同，C和C++中就是连续的，在上C语言或者C++课程时，总会遇到计算内存地址的相关题目。

在C++中，按照规范的方式来划分的话，Vector应该属于容器，其底层实现是Array，还是有所区别的。

补充Vector和Array的相关内容

暴力解法时间复杂度是n，使用二分查找能做到logn。

做这种类型题目时，确定好循环终结的条件就好，不要混乱，一般都能写出来。

❓

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

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

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

示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。

示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

这里首次引入了双指针的思想，简单来说，第一个指针找到下一个需要安放的位置，第二个指针去找适合安放的元素。

这里要注意，不一定双指针就一定都从左往右移，要根据具体情况具体分析。

这类问题比较经典，难度从低到高的都有。

滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)的暴力解法降为O(n)。

这部分就开始复杂起来了，因为我们这里面需要很好地处理窗口左右边界移动地时机，在做题时，还需要借助哈希表等容器辅助。

熟悉大部分的C++标准容器

典型题目就是leetcode上的两个螺旋矩阵问题，这部分乍一看是比较简单的，但是难就难在边界条件处理时十分头疼。在做这类题目是，头脑一定要清晰，如何遍历？如何制定统一的遍历判断，使代码编写时不容易乱，需要非常注意。

刷完这部分题目，日程安排上需要加入两个新的内容，一个是如何自行处理输入输出；一个是重新拾回数据结构，并熟悉C++、C#中常见的容器及其实现原理。

💡

Written by Aryue，editted by Notion AI.