数组

学习数据结构与算法
2021-05-17 14:29 · 阅读时长12分钟
小课

数组是多个相同类型或者说相同大小数据的集合,它在内存中是连续存储,可以根据索引快速定位某个元素。数组有以下几个特点。

  1. 数组中的元素在内存中是连续存储。
  2. 数组长度在定义数组时指定,不可更改。
  3. 数组中的元素必须是相同类型。
  4. 可以通过数组+索引的方式快速定位某个元素。

数组的优点有访问快,直接通过索引访问,时间复杂度为O(1),但是插入和删除的时间复杂为O(N)。

例如,数组[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]的存储结构如下:

关于数组的更多介绍可参考维基百科

注释
加载中...

对于数组,我们可以通过下标的方式获取指定元素,比如数组array=[1,2,3,4,5,6,7,8,9,10],可以通过array[7]来获取元素8,注意下标从0开始,同样也可以通过array[7]=0,这种方式来修改指定位置的元素。

从维度上来看,上面的array数组我们称之为一维数组,如果数组的元素也是一个数组,那么种数组就称为多维数组,比如

二维数组

[[1, 2, 3], [4, 5, 6]]

三维数组

[[[1, 2], [3, 4]], [[5, 6], [7, 8]]]

对于多维数组,我们同样可以通过下标的方式获取指定位置的元素,比如获取上面二维数组中的元素4,可以通过array[1][0]来获取。

数组是非常基础的数据结构,很多其它数据结构的底层数据存储方式都可以用数组来实现。比如说List,Map、Stack、Queue等等。

通常数组下标是从0开始,但是也有一些编程语言并非如此。

注释
加载中...

解决数组相关的算法问题常用的技巧有双指针滑动窗口,以下是几道比较经典的题目。

颜色分类问题

给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

示例 1:

输入:nums = [2,0,2,1,1,0] 
输出:[0,0,1,1,2,2]

示例 2:

输入:nums = [2,0,1]
输出:[0,1,2]

示例 3:

输入:nums = [0]
输出:[0]

示例 4:

输入:nums = [1]
输出:[1]

提示:

  • n == nums.length
  • 1 <= n <= 300
  • nums[i] 为 0、1 或 2

这道题有很多种解法,最容易想到就是对数组进行排序,这里的元素只有三个,所以非常适合用计数排序。在特定的条件下,计数排序相对于比较类的排序算法效率要高很多,能达到线性级别时间复杂度O(N+K)。

查看计数排序课程

注释
加载中...

使用双指针的解法,主要思路是,因为总共有红色(0)、白色(1)和蓝色(2)三种颜色,所以我们只需要将红色移动到数组前面部分,将蓝色移动到数组后面部分,剩下的白色自然就是数组中间,这样就将三种颜色按序排列好了。

加载中...
两数之和 II - 输入有序数组

给定一个已按照升序排列的整数数组 numbers,请你从数组中找出两个数满足相加之和等于目标数target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers的下标从 1 开始计数,所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。

你可以假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素。

示例 1:

输入:numbers = [2,7,11,15], target = 9
输出:[1,2]
解释:2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

示例 2:

输入:numbers = [2,3,4], target = 6
输出:[1,3]

示例 3:

输入:numbers = [-1,0], target = -1
输出:[1,2]

提示:

  • 2 <= numbers.length <= 3 * 10^4
  • -1000 <= numbers[i] <= 1000
  • numbers 按 递增顺序 排列
  • -1000 <= target <= 1000
  • 仅存在一个有效答案

主要思路是,定义两个指针,从数组前后两端向中间移动,由于数组本身是升序排列,所以如果两个指针当前元素的和小于目标值,则前面的指针后移;如果大于目标值,则后面的指针往前移,直到两者相等。该题也可以用哈希表表的方式来解,但是这样就没有利用上数组本身是有序的条件,而且空间复杂度比双指针的解法要高一些。

加载中...
数组array