没有域名怎么访问网站,东莞网站设计报价,网站开发还找到工作吗,那个网站学做披萨比较好文章目录一#xff1a;数组理论基础二#xff1a;数组这种数据结构的优点和缺点是什么#xff1f;三#xff1a;数组是如何实现随机访问的呢#xff1f;四#xff1a;低效的“插入”和“删除”原因在哪里#xff1f;五#xff1a;实战解题1. 移除元素暴力解法双指针法2… 文章目录一数组理论基础二数组这种数据结构的优点和缺点是什么三数组是如何实现随机访问的呢四低效的“插入”和“删除”原因在哪里五实战解题1. 移除元素暴力解法双指针法2.有序数组的平方暴力解法双指针法最后说一句作者简介大家好我是黑洞晓威一名大二学生希望和大家一起进步。 本文收录于 算法本专栏是针对大学生、初学算法的人准备解析常见的数据结构与算法同时备战蓝桥杯。 一数组理论基础
首先要知道数组在内存中的存储方式这样才能真正理解数组相关的题
数组是存放在连续内存空间上的相同类型数据的集合。
数组可以方便的通过下标索引的方式获取到下标下对应的数据。
举一个字符数组的例子如图所示 需要两点注意的是
数组下标都是从0开始的。数组内存空间的地址是连续的
正是因为数组的在内存空间的地址是连续的所以我们在删除或者增添元素的时候就难免要移动其他元素的地址。
例如删除下标为3的元素需要对下标为3的元素后面的所有元素都要做移动操作如图所示 二数组这种数据结构的优点和缺点是什么 优点查询/查找/检索某个下标上的元素时效率极高。 原因
第一每一个元素的内存地址在空间存储上是连续的。
第二每一个元素类型相同所以占用空间大小一样。
第三知道第一个元素内存地址知道每一个元素占用空间的大小又知道下标所以通过一个数学表达式就可以计算出某个下标上元素的内存地址。直接通过内存地址定位元素所以数组的检索效率是最高的。 注意
缺点 第一由于为了保证数组中每个元素的内存地址连续所以在数组上随机删除或者增加元素的时候效率较低因为随机增删元素会涉及到后面元素统一向前或者向后位移的操作。 第二数组不能存储大数据量。 因为很难在内存空间上找到一块特别大的连续的内存空间。 注意 对于数组中最后一个元素的增删是没有效率影响的。
三数组是如何实现随机访问的呢
数组Array是一种线性表数据结构。它用一组连续的内存空间来存储一组具有相同类型的数据。
这个定义里有几个关键词理解了这几个关键词我想你就能彻底掌握数组的概念了。下面就从我的角度分别给你“点拨”一下。
第一是 线性表Linear List。顾名思义线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组链表、队列、栈等也是线性表结构。 而与它相对立的概念是 非线性表比如二叉树、堆、图等。之所以叫非线性是因为在非线性表中数据之间并不是简单的前后关系。 第二个是 连续的内存空间和相同类型的数据。正是因为这两个限制它才有了一个堪称“杀手锏”的特性“随机访问”。但有利就有弊这两个限制也让数组的很多操作变得非常低效比如要想在数组中删除、插入一个数据为了保证连续性就需要做大量的数据搬移工作。
说到数据的访问那你知道数组是如何实现根据下标随机访问数组元素的吗
我们拿一个长度为10的int类型的数组int[] a new int[10]来举例。在我画的这个图中计算机给数组a[10]分配了一块连续内存空间10001039其中内存块的首地址为base_address 1000。 我们知道计算机会给每个内存单元分配一个地址计算机通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时它会首先通过下面的寻址公式计算出该元素存储的内存地址
a[i]_address base_address i * data_type_size其中data_type_size表示数组中每个元素的大小。我们举的这个例子里数组中存储的是int类型数据所以data_type_size就为4个字节。这个公式非常简单我就不多做解释了。
这里我要特别纠正一个“错误”。问到数组和链表的区别很多人都回答说“链表适合插入、删除时间复杂度O(1)数组适合查找查找时间复杂度为O(1)”。
实际上这种表述是不准确的。数组是适合查找操作但是查找的时间复杂度并不为O(1)。即便是排好序的数组你用二分查找时间复杂度也是O(logn)。所以正确的表述应该是数组支持随机访问根据下标随机访问的时间复杂度为O(1)。
四低效的“插入”和“删除”原因在哪里
前面概念部分我们提到数组为了保持内存数据的连续性会导致插入、删除这两个操作比较低效。现在我们就来详细说一下究竟为什么会导致低效又有哪些改进方法呢
我们先来看 插入操作。
假设数组的长度为n现在如果我们需要将一个数据插入到数组中的第k个位置。为了把第k个位置腾出来给新来的数据我们需要将第kn这部分的元素都顺序地往后挪一位。那插入操作的时间复杂度是多少呢你可以自己先试着分析一下。
如果在数组的末尾插入元素那就不需要移动数据了这时的时间复杂度为O(1)。但如果在数组的开头插入元素那所有的数据都需要依次往后移动一位所以最坏时间复杂度是O(n)。 因为我们在每个位置插入元素的概率是一样的所以平均情况时间复杂度为(12…n)/nO(n)。
如果数组中的数据是有序的我们在某个位置插入一个新的元素时就必须按照刚才的方法搬移k之后的数据。但是如果数组中存储的数据并没有任何规律数组只是被当作一个存储数据的集合。在这种情况下如果要将某个数据插入到第k个位置为了避免大规模的数据搬移我们还有一个简单的办法就是直接将第k位的数据搬移到数组元素的最后把新的元素直接放入第k个位置。
为了更好地理解我们举一个例子。假设数组a[10]中存储了如下5个元素abcde。
我们现在需要将元素x插入到第3个位置。我们只需要将c放入到a[5]将a[2]赋值为x即可。最后数组中的元素如下 abxdec。 利用这种处理技巧在特定场景下在第k个位置插入一个元素的时间复杂度就会降为O(1)。这个处理思想在快排中也会用到我会在排序那一节具体来讲这里就说到这儿。
我们再来看 删除操作。
跟插入数据类似如果我们要删除第k个位置的数据为了内存的连续性也需要搬移数据不然中间就会出现空洞内存就不连续了。
和插入类似如果删除数组末尾的数据则最好情况时间复杂度为O(1)如果删除开头的数据则最坏情况时间复杂度为O(n)平均情况时间复杂度也为O(n)。
实际上在某些特殊场景下我们并不一定非得追求数组中数据的连续性。如果我们将多次删除操作集中在一起执行删除的效率是不是会提高很多呢
我们继续来看例子。数组a[10]中存储了8个元素abcdefgh。现在我们要依次删除abc三个元素。 为了避免defgh这几个数据会被搬移三次我们可以先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据只是记录数据已经被删除。当数组没有更多空间存储数据时我们再触发执行一次真正的删除操作这样就大大减少了删除操作导致的数据搬移。
五实战解题
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(vectorint 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:vectorint sortedSquares(vectorint 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;}
}最后说一句
感谢大家的阅读文章通过网络资源与自己的学习过程整理出来希望能帮助到大家。
才疏学浅难免会有纰漏如果你发现了错误的地方可以提出来我会对其加以修改。
