数组是非常基础的数据结构,在面试中,考察数组的题目一般在思维上都不难,主要是考察对代码的掌控能力
也就是说,想法很简单,但实现起来 可能就不是那么回事了
首先要知道数组在内存中的存储方式,这样才能真正理解数组相关的面试题
数组是存放在连续内存空间上的相同类型数据的集合。
数组可以方便的通过下表索引的方式获取到下表下对应的数据。
举一个字符数组的例子,如图所示:
需要两点注意的是
正是因为数组的在内存空间的地址是连续的,所以我们在删除或者增添元素的时候,就难免要移动其他元素的地址
例如删除下表为3的元素,需要对下表为3的元素后面的所有元素都要做移动操作,
如图所示:
时间复杂度为O(n),所以数组不适合做频繁的增删操作 ,这一点在以后解题选择容器的时候中也是非常重要的。
至于二维数组,直接上图,大家应该就知道怎么回事了,图中a[][]表示的就是二维数组
二维数组其实就是一个矩阵
那么二维数组在内存的空间地址是连续的么?
我们来举一个例子,例如: int[][] rating = new int[3][4];
, 这个二维数据在内存空间可不是一个 3*4
的连续地址空间
如图所示:
二位数组中其实是一个线性数组存放着 其他数组的首地址。
所以二维数据在内存中不是 3*4
的连续地址空间,而是四条连续的地址空间组成!
很多同学会以为二维数组在内存中是一片连续的地址,其实并不是。
这里面试中数组相关的理论知识就介绍完了。
后续我将介绍面试中数组相关的五道经典面试题目,敬请期待!