在每一种编程语言中,都会有数组这种数据类型。不过,它不仅仅是一种编程语言中的数据类型,还是一种最基础的数据结构。尽管数组看起来非常基础、简单,但很多人并没有理解这个基础数据结构的精髓。
什么是数组?
数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。
这里有几个关键词给大家解释一下,帮助大家更深刻的认识数组,它们分别是:线性表数据结构
、连续内存空间
、相同类型
。
线性表数据结构
在前面 《复杂度分析》那篇文章中,数据结构按照逻辑结构大致可以分为两类:线性数据结构和非线性数据结构。线性数据结构即数据之间存在着一对一的线性关系,是一组数据的有序集合。
数组在内存中的存储结构就是一种线性数据结构,数组有一个头节点索引为0和尾节点索引为数组长度 length-1
连续内存空间
内存空间是否连续是数组和链表的最大区别!举个例子:
数组需要一块连续的内存空间来存储,对内存的要求比较高。如果我们申请一个 100MB 大小的数组,当内存中没有连续的、足够大的存储空间时,即便内存的剩余总可用空间大于 100MB,仍然会申请失败。而链表恰恰相反,它并不需要一块连续的内存空间,它通过“指针”将一组零散的内存块串联起来使用,所以如果我们申请的是 100MB 大小的链表,根本不会有问题。
相同类型
我们知道数组在定义时已经可以确定数组的类型和大小,比如 int[] a = new int[10]; 这是定义一个大小为10的int 类型数组并初始化为0。
数组是可以根据下标实现随机访问的,那么它是如何实现的呢?我们拿之前定义的 a 数组举例:
计算机给数组 a[10],分配了一块连续内存空间 1000~1039,其中,内存块的首地址为 base_address = 1000。
![]()
我们知道,计算机会给每个内存单元分配一个地址,计算机通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时,它会首先通过下面的寻址公式,计算出该元素存储的内存地址:
a[i]_address = base_address + i * data_type_size
其中 data_type_size 表示数组中每个元素的大小。这个例子里,数组中存储的是 int 类型数据,所以 data_type_size 就为 4 个字节。这个公式非常简单,就不多做解释了。
数组的特性
- 数组是存储多个相同类型的数据集合
- 数组在定义时已经固定长度
- 数组占有连续的内存空间
- 对数据进行下标随机访问时间复杂度O(1)
数组是其他数据类型的基础
为什么说数组是一种基本的数据类型?
第一:数组这种数据类型太常用了 ,基本每个编程语言都有;第二:数组还构成了其他数据类型。
数组构成了哪些数据类型?
- 数组可以表示完全二叉树结构
- 数组可以表示顺序栈结构
- 数组可以表示顺序队列结构
- 数组可以实现Java的ArrayList,实现动态扩容
数组增删改查操作
从前面对数组的定义中我们知道,数据根据下标可以实现随机访问,所以数组的查询时间复杂度O(1);但是数组在内存中是连续的内存空间,对数组进行 增加、删除 操作时,为了保持内存空间的连续性,操作的时间复杂度为 O(n)。
数组插入操作
假设数组的长度为 n,现在,如果我们需要将一个数据插入到数组中的第 k 个位置。为了把第 k 个位置腾出来,给新来的数据,我们需要将第 k~n 这部分的元素都顺序地往后挪一位。那插入操作的时间复杂度是多少呢?你可以自己先试着分析一下。
如果在数组的末尾插入元素,那就不需要移动数据了,这时的时间复杂度为 O(1)。但如果在数组的开头插入元素,那所有的数据都需要依次往后移动一位,所以最坏时间复杂度是 O(n)。 因为我们在每个位置插入元素的概率是一样的,所以平均情况时间复杂度为 (1+2+…n)/n=O(n)。
为了更好的理解,我们举一个例子:
假设数组 a[10]中存储了如下 5 个元素:a,b,c,d,e。我们需要将元素 x 插入到第 3 个位置。
![]()
数组删除操作
跟插入数据类似,如果我们要删除第 k 个位置的数据,为了内存的连续性,也需要搬移数据,不然中间就会出现空洞,内存就不连续了。
和插入类似,如果删除数组末尾的数据,则最好情况时间复杂度为 O(1);如果删除开头的数据,则最坏情况时间复杂度为 O(n);平均情况时间复杂度也为 O(n)。
为了更好的理解,我们举一个例子:
假设数组 a[10]中存储了如下 5 个元素:a,b,c,d,e。我们需要将第3个位置的元素移除。
![]()
数组的应用
219. 存在重复元素 II
题目
给定一个整数数组和一个整数 k,判断数组中是否存在两个不同的索引 i 和 j,使得 nums [i] = nums [j],并且 i 和 j 的差的 绝对值 至多为 k。
解题分析
方法1:利用哈希表Map
可以利用辅助空间哈希表HashMap,其中 key为数组索引i对应的值,value为数组索引i
- 如果hash表中不存在重复的值,将该值及其对应的索引存入hash表中
- 如果hash表中存在重复的值,比较该值的重复索引差值,如果满足 <= k,返回true,否则将value更新为最新的索引
方法2:利用哈希表Set + 滑动窗口
- 遍历数组,对于每个元素做以下操作:
- 在散列表中搜索当前元素,如果找到了就返回 true。
- 在散列表中插入当前元素。
- 如果当前散列表的大小超过了 kk, 删除散列表中最旧的元素。
- 返回 false。
复杂度分析
时间复杂度:O(n) 其中n为数组大小,最坏情况下需要遍历整个数组
空间复杂度:O(n) 其中n为数组大小,最坏情况下需要存储整个数组
代码
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
if(nums == null || nums.length <= 1){
return false;
}
Map<Integer,Integer> hash = new HashMap<Integer,Integer>();
for(int i = 0 ; i < nums.length ; i ++) {
if (hash.containsKey(nums[i])){
if (Math.abs(hash.get(nums[i]) - i) <= k){
return true;
}
}
hash.put(nums[i],i);
}
return false;
}
}
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
HashSet<Integer> set = new HashSet<>();
for(int i = 0; i < nums.length; i++) {
if(set.contains(nums[i])) {
return true;
}
set.add(nums[i]);
if(set.size() > k) {
set.remove(nums[i - k]);
}
}
return false;
}
}
1438. 绝对差不超过限制的最长连续子数组
题目
给你一个整数数组 nums ,和一个表示限制的整数 limit,请你返回最长连续子数组的长度,该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。
如果不存在满足条件的子数组,则返回 0 。
4. 寻找两个正序数组的中位数
题目
给定两个大小为 m 和 n 的正序(从小到大)数组
nums1
和nums2
。请你找出并返回这两个正序数组的中位数。