第 3 关 | 爱不起的数组与双指针思想：1. 青铜挑战——爱不起的数组-灵析社区
时光小少年1. 线性表基础
1.1. 线性表
我们先搞清楚几个基本概念，在很多地方会看到线性结构、线性表这样的表述，那什么是线性结构？与数组、链表等有什么关系？常见的线性结构又有哪些呢？
所谓线性表就是具有相同特征数据元素的一个有限序列，其中所含元素的个数称为线性表的长度，从不同的角度看，线性表可以有不同的分类，例如：
从语言实现的角度顺序表有两种基本实现方式，一体式和分离式，如下：
图a为一体式结构，存储表信息的单元与元素存储区以连续的方式安排在一块存储区里，两部分数据的整体形成一个完整的顺序表对象。这种结构整体性强，易于管理。但是由于数据元素存储区域是表对象的一部分，顺序表创建后，元素存储区就固定了。C和C++都是一体式的结构。
图b为分离式结构，表对象里只保存与整个表有关的信息（即容量和元素个数），实际数据元素存放在另一个独立的元素存储区里，通过链接与基本表对象关联。Java和python是分离式结构。
从存储的角度
从存储的角度看，可以分为顺序型和链表型。顺序性就是将数据存放在一段固定的区间内，此时访问元素的效率非常高，但是删除和增加元素代价比较大，如果要扩容只能整体搬迁。
而在链表型里，元素之间是通过地址依次连接的，因此访问时必须从头开始逐步向后找，因此查找效率低，而删除和增加元素非常方便，并且也不需要考虑扩容的问题。链表的常见实现方式又有单链表、循环链表、双向链表等等等。
从访问限制的角度
栈和队列又称为访问受限的线性表，插入和删除受到了限制，只能在固定的位置进行。而Hash比较特殊，其内部真正存储数据一般是数组，但是访问是通过映射来实现的，因此大部分材料里并不将Hash归结到线性表中，这里为了学习更紧凑，我们将其与队栈一起学习。线性表的知识框架如下：
线性表的常见操作有初始化、求表长、增删改查等，事实上每种数据结构都至少要有这几种操作，大部分的基础算法题都是基于此扩展的。
从扩容的角度
采用分离式结构的顺序表，若将数据区更换为存储空间更大的区域，则可以在不改变表对象的前提下对其数据存储区进行了扩充，所有使用这个表的地方都不必修改。只要程序的运行环境（计算机系统）还有空闲存储，这种表结构就不会因为满了而导致操作无法进行。人们把采用这种技术实现的顺序表称为动态顺序表，因为其容量可以在使用中动态变化。
扩充的两种策略：
●第一种：每次扩充增加固定数目的存储位置，如每次扩充增加10个元素位置，这种策略可称为线性增长。特点：节省空间，但是扩充操作频繁，操作次数多。
●第二种：每次扩充容量加倍，如每次扩充增加一倍存储空间。特点：减少了扩充操作的执行次数，但可能会浪费空间资源。以空间换时间，推荐的方式。
具体到每种结构语言中的结构，实现方式千差万别。其中Java基本是扩容时加倍的方式。而在Python的官方实现中，list实现采用了如下的策略：在建立空表（或者很小的表）时，系统分配一块能容纳8个元素的存储区；在执行插入操作（insert或append）时，如果元素存储区满就换一块4倍大的存储区。但如果此时的表已经很大（目前的阀值为50000），则改变策略，采用加一倍的方法。引入这种改变策略的方式，是为了避免出现过多空闲的存储位置。
1.2. 数组的概念
数组是线性表最基本的结构，特点是元素是一个紧密在一起的序列，相互之间不需要记录彼此的关系就能访问，例如月份、星座等。
数组用索引的数字来标识每项数据在数组中的位置，且在大多数编程语言中，索引是从 0 算起的。我们可以根据数组中的索引快速访问数组中的元素。
数组有两个需要注意的点，一个是从0开始记录，也就是第一个存元素的位置是a[0]，最后一个是a[length-1]。其次，数组中的元素在内存中是连续存储的，且每个元素占用相同大小的内存。
另外需要注意的是数组空间不一定是满的，100的空间可能只用了10个位置，所以要注意数据个数的变量size和数组长度length可能不一样，解题时必须注意。
1.3. 数组存储元素的特征
在往期训练营中，发现很多学员对数组如何存储元素的并不太清楚，这里采用连环炮方式来说明。
第一炮，我创建了一个大小为10的数组，请问此时数组里面是什么？
答：不同的语言处理会不一样，在c语言里每个位置都是一个随机数。而在java里，默认会初始化为0。而python更为灵活可以直接指定是什么，例如a = [1,2,3,4]，就是数组里有四个元素，而a = [0 for i in range(10)]这样定义的数组就是[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
第二炮：是否可以只初始化一部分位置？初始化的本质是什么？
答：当然可以，你可以将前面5个位置依次，后面的空着，此时数组内容为{1,2,3,4,5,0,0,0,0,0}。
初始化的本质就是覆盖已有的值，用你需要的值覆盖原来的0，因为数组本来是{0,0,0,0,0,0,0,0,0,0}，这里只不过被你替换成了{1,2,3,4,5,0,0,0,0,0}。如果此时你想知道有效元素的个数，就必须再使用一个额外的变量，例如size来标记。
第三炮：上面已经初始化的元素之间是否可以空着，例如初始化为{1,0,0,4,5,0,2,0,3,0}。其中0位置仍然是未初始化的？
答：不可以！绝对不可以！要初始化，就必须从前向后的连续空间初始化，不可以出现空缺的情况，这是违背数组的原则的。你正在进行某种运算期间可以先给部分位置赋值，而一旦稳定了，就不可以再出现空位置的情况。
第四炮：如果我需要的数据就是在中间某一段该怎么办呢？例如{0,0,3,4,5,6,7,0,0,0}，此时该怎么拿到从3到7的元素呢？
答：你需要使用两个变量，例如left=2，right=6来表示区间[left,right]是有效的。
第五炮：我删除的时候，已经被删除的位置该是什么呢？例如原始数组为{1,2,3,4,5,6,7,8,0,0}，我删除4之后，根据数组的移动原则，从5开始向前移动，变成{1,2,3,5,6,7,8,?,0,0}，那原来8所在的位置应该是什么呢？
答：仍然是8，也就是删除4之后的结构为{1,2,3,5,6,7,8,8,0,0}，此时表示元素数量的size会减1变成7，原来8的位置仍然是8。因为我们是通过size来标记元素数量的，所以最后一个8不会被访问到。
第六炮：这个里8看起来很不爽啊，是否可以再优化一下？
答：不爽就不爽，习惯就好！不用优化，优化了也没啥用。
2. 数组基本操作
在面试中，数组大部分情况下都是int类型的，所以我们就用int类型来实现这些基本功能。
2.1. 数组创建和初始化
创建一维数组的方法不同的语言不一样的，如下：
int[] arr = new int[10];
a[]={1,2,2,1,0,2,4,2,3,1};
list = []
接下来的代码，不同的语言大同小异，也比较简单，我们就不再提供每种语言的实现了，同学们可以自己来写一写。
初始化数组最基本的方式是循环赋值：
for(int i = 0 ; i < arr.length ; i ++){
arr[i] = i;
}
但是这种方式在面试题中一般不行，因为很多题目会给定若干测试数组让你都能测试通过，例如给你两个数组[0,1,2,3,5,6,8] 和 [1,4,5,6,7,9,10] 。那这时候该如何初始化呢？显然不能用循环了，可以采用下面的方式：
int[] arr = new int[]{0,1,2,3,4,5,6,8};
//这么写也可以
int[] nums = {2,5,0,4,6,-10};
如果要测试第二组数据，直接将其替换就行了。这种方式很简单，在面试时特别实用，但是务必记住写法，否则面试时可能慌了或者忘了，老写不对，这会让你无比着急，想死的心都有! 我们练习算法的一个目标就是熟悉这些基本问题，避免阴沟里翻船。
另外要注意上面在创建数组时大小就是元素的数量，是无法再插入元素的，如果需要增加新元素就不能这么用了。
作业：
将int[] nums = {2, 5, 0, 4, 6, -10}这种赋值方法背下来。
是的！！！背下来，没什么好说的。
2.2. 查找一个元素
为什么数组的题目特别多呢，因为很多题目本质就是查找问题，而数组是查找的最佳载体。很多复杂的算法都是为了提高查找效率的，例如二分查找、二叉树、红黑树、B+树、Hash和堆等等。另一方面很多算法问题本质上都是查找问题，例如滑动窗口问题、回溯问题、动态规划问题等等都是在寻找那个目标结果。
这里只写最简单的方式，根据值是否相等进行线性查找，基本实现如下：
/**
* @param size 已经存放的元素个数
* @param key 待查找的元素
*/
public static int findByElement(int[] arr, int size, int key) {
for (int i = 0; i < size; i++) {
if (arr[i] == key)
return i;
}
return -1;
}
def findByElement(arr, size, key):
for i in range(size):
if arr[i] == key:
return i
return -1
int findByElement(int arr[], int size, int key)
{
for (int i = 0; i < size; i++)
{
if (arr[i] == key)
{
return i;
}
}
return -1;
}
作业
还有一种很常见的情况，如果数组是递增的，此时查找时如果相等或者当前位置元素比目标值更大就停下了。 你是否可以修改上面的代码来实现这个功能？
2.3. 增加一个元素
增加和删除元素是数组最基本的操作，看别人的代码非常容易，但是自己写的时候经常bug满天飞。能准确处理游标和边界等情况是数组算法题最基础重要的问题之一。所以务必自己亲手能写一个才可以，不要感觉挺简单就不写，其中涉及的问题在所有与数组有关的算法题中都会遇到。
面试冒汗时别怪没提醒！！！！
将给定的元素插入到有序数组的对应位置中，我们可以先找位置，再将其后元素整体右移，最后插入到空位置上。这里需要注意，算法必须能保证在数组的首部、尾部和中间位置插入都可以成功。该问题貌似一个for循环就搞定了，但是如果面试直接让你写并能正确运行，我相信很多人还是会折腾很久，甚至直接会挂。因为自己写的时候会发现游标写size还是size-1，判断时要不要加等于等等，这里推荐一种实现方式。
/**
* @param arr
* @param size 数组已经存储的元素数量，从1开始编号
* @param element 待插入的元素
* @return
*/
public static int addByElementSequence(int[] arr, int size, int element) {
//问题①：是否应该是size>arr.length
if (size >= arr.length)
retrun -1;
//问题②想想这里是否是index=0或者size-1？
int index = size;
//找到新元素的插入位置，问题③ 这里是否应该是size-1？
for (int i = 0; i < size; i++) {
if (element < arr[i]) {
index = i;
break;
}
}
//元素后移，问题④想想这里为什么不是size-1
for (int j = size; j > index; j--) {
arr[j] = arr[j - 1]; //index下标开始的元素后移一个位置
}
arr[index] = element;//插入数据
return index;
}
def addByElementSequence(arr, size, element):
if size >= len(arr):
return -1
index = size
for i in range(size):
if element < arr[i]:
index = i
break
for j in range(size, index, -1):
arr[j] = arr[j - 1]
arr[index] = element
return index
int addByElementSequence(int arr[], int size, int element)
{
if (size >= sizeof(arr) / sizeof(arr[0]))
{
return -1;
int index = size;
for (int i = 0; i < size; i++)
{
if (element < arr[i])
{
index = i;
break;
}
}
for (int j = size; j > index; j--)
{
arr[j] = arr[j - 1];
}
}
}
上面的代码在往期课程里被提出疑问特别多，主要是标记编号的几个位置，这几个全都是边界问题。这里回答几个：
问题①处，注意这里的size是从1开始编号的，表示的就是实际元素的个数。而arr.length也是从1开始的，当空间满的时候就是size=arr.length，此时就不能再插入元素了。
问题② 处只能令index=size， 0或者size-1都不对。例如已有序列为{3,4,7,8}，如果插入的元素比8大，例如9，假如index=0，则最后结果是{9,3,4,7,8}。假如index=size-1，最后结果就是{3,4,7,9,8}。
问题③和④处，这个就不用解释了吧，请读者自己思考。
作业
除了上面的方式，还可以一开始就从后向前一边移动一边对比查找，找到位置直接插入。从效率上看这样更好一些，因为只遍历了一次，你是否可以实现一下呢？
2.4. 删除一个元素
对于删除，不能一边从后向前移动一边查找了，因为元素可能不存在。
所以要分为两个步骤，先从最左侧开始查是否存在元素，如果元素存在，则从该位置开始执行删除操作。
例如序列是 1 2 3 4 5 6 7 8 9 ，要删除5，则应先遍历，找到5，然后从5开始执行删除操作，也就是从6开始逐步覆盖上一个元素，最终将序列变成 1 2 3 4 6 7 8 9 [9]。
这个方法和增加元素一样，必须自己亲自写才有作用，该方法同样要求删除序列最前、中间、最后和不存在的元素都能有效，下面给一个参考实现：
/**
* 从数组中删除元素key
* @param arr 数组
* @param size 数组中的元素个数，从1开始
* @param key 删除的目标值
*/
public int removeByElement(int[] arr, int size, int key) {
int index = -1;
for (int i = 0; i < size; i++) {
if (arr[i] == key) {
index = i;
break;
}
}
if (index != -1) {
for (int i = index + 1; i < size; i++)
arr[i - 1] = arr[i];
size--;
}
return size;
}
int removeByElement(int arr[], int size, int key)
{
int index = -1;
for (int i = 0; i < size; i++)
{
if (arr[i] == key)
{
index = i;
break;
}
}
if (index != -1)
{
for (int i = index + 1; i < size; i++)
{
arr[i - 1] = arr[i];
}
size--;
}
return size;
}
def removeByElement(arr, size, key):
index = -1
for i in range(size):
if arr[i] == key:
index = i
break
if index != -1:
for i in range(index + 1, size):
arr[i - 1] = arr[i]
size -= 1
return size
3. 算法热身——单调数组问题
先看个热身问题，我们在写算法的时候，数组是否有序是一个非常重要的前提，有或者没有可能会采用完全不同的策略。 LeetCode 896.判断一个给定的数组是否为单调数组。
分析：如果对于所有 i <= j，A[i] <= A[j]，那么数组 A 是单调递增的。 如果对于所有 i <= j，A[i]> = A[j]，那么数组 A 是单调递减的。所以遍历数组执行这个判定条件就行了，由于有递增和递减两种情况。于是我们执行两次循环就可以了，代码如下：
public boolean isMonotonic(int[] nums) {
return isSorted(nums, true) || isSorted(nums, false);
}
public boolean isSorted(int[] nums, boolean increasing) {
int n = nums.length;
for (int i = 0; i < n - 1; ++i) {
if(increasing){
if (nums[i] > nums[i + 1]) {
return false;
}
}else{
if (nums[i] < nums[i + 1]) {
return false;
}
}
}
return true;
}
bool isSorted(int* nums, int numsSize, bool increasing) {
for (int i = 0; i < numsSize - 1; ++i) {
if (increasing) {
if (nums[i] > nums[i + 1]) {
return false;
}
} else {
if (nums[i] < nums[i + 1]) {
return false;
}
}
}
return true;
}
bool isMonotonic(int* nums, int numsSize) {
return isSorted(nums, numsSize, true) || isSorted(nums, numsSize, false);
}
def isMonotonic(nums):
return isSorted(nums, True) or isSorted(nums, False)
def isSorted(nums, increasing):
n = len(nums)
for i in range(n-1):
if increasing:
if nums[i] > nums[i+1]:
return False
else:
if nums[i] < nums[i+1]:
return False
return True
这样虽然实现功能了，貌似有点繁琐，而且还要遍历两次，能否优化一下呢？假如我们在i和i+1位置出现了nums[i]>nums[i+1],而在另外一个地方j和j+1出现了nums[j]<nums[j+1]，那是不是说明就不是单调了呢？这样我们就可以使用两个变量标记一下就行了，代码如下：
public boolean isMonotonic(int[] nums) {
boolean inc = true, dec = true;
int n = nums.length;
for (int i = 0; i < n - 1; ++i) {
if (nums[i] > nums[i + 1]) {
inc = false;
}
if (nums[i] < nums[i + 1]) {
dec = false;
}
}
return inc || dec;
}
bool isMonotonic(int* nums, int numsSize) {
bool inc = true, dec = true;
for (int i = 0; i < numsSize - 1; ++i) {
if (nums[i] > nums[i + 1]) {
inc = false;
}
if (nums[i] < nums[i + 1]) {
dec = false;
}
}
return inc || dec;
}
def isMonotonic(nums):
inc = True
dec = True
n = len(nums)
for i in range(n - 1):
if nums[i] > nums[i + 1]:
inc = False
if nums[i] < nums[i + 1]:
dec = False
return inc or dec
我们判断整体单调性不是白干的，很多时候需要将特定元素插入到有序序列中，并保证插入后的序列仍然有序，例如leetcode35：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
示例1：
输入: nums = [1,3,5,6], target = 5
存在5，并且在索引为2的位置，所以输出: 2
示例2：
输入: nums = [1,3,5,6], target = 2
不存在2，2插入之后在索引为1的位置，所以输出: 1
这个问题没有让你将新元素插入到原始序列中，还是比较简单的，只要遍历一下就找到了。如果面试官再问你，该如何更快的找到目标元素呢？那他其实是想考你二分查找。以后凡是提到在单调序列中查找的情况，我们应该马上想到是否能用二分来提高查找效率。二分的问题我们后面专门讨论，这里只看一下实现代码：
public int searchInsert(int[] nums, int target) {
int n = nums.length;
int left = 0, right = n - 1, ans = n;
while (left <= right) {
int mid = ((right - left) >> 1) + left;
if (target <= nums[mid]) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
int searchInsert(int* nums, int numsSize, int target) {
int left = 0, right = numsSize - 1, ans = numsSize;
while (left <= right) {
int mid = ((right - left) >> 1) + left;
if (target <= nums[mid]) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
def searchInsert(nums, target):
n = len(nums)
left = 0
right = n - 1
ans = n
while left <= right:
mid = (right - left) // 2 + left
if target <= nums[mid]:
ans = mid
right = mid - 1
else:
left = mid + 1
return ans
4. 算法热身—数组合并专题
数组合并就是将两个或者多个有序数组合并成一个新的。这个问题的本身不算难，但是要写的够出彩才可以。还有后面要学的归并排序本身就是多个小数组的合并，所以研究该问题也是为了后面打下基础。
先来看如何合并两个有序数组，LeetCode88：给你两个按非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。请你合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 应忽略。nums2 的长度为 n 。
例子1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：合并 [1,2,3] 和 [2,5,6] 的结果是 [1,2,2,3,5,6]
对于有序数组的合并，一种简单的方法是先将B直接合并到A的后面，然后再对A排序，也就是这样:
public void merge1(int[] nums1, int nums1_len, int[] nums2, int nums2_len) {
for (int i = 0; i < nums2_len; ++i) {
nums1[nums1_len + i] = nums2[i];
}
Arrays.sort(nums1);
}
但是这么写只是为了开拓思路，面试官会不喜欢，太没技术含量了。这个问题的关键是将B合并到A的仍然要保证有序。因为A是数组不能强行插入，如果从前向后插入，数组A后面的元素会多次移动，代价比较高。此时可以借助一个新数组C来做，先将选择好的放入到C中，最后再返回。这样虽然解决问题了，但是面试官可能会问你能否再优化一下，或者不申请新数组就能做呢？更专业的问法是：上面算法的空间复杂度为O(n)，能否有O(1)的方法？
比较好的方式是从后向前插入，A和B的元素数量是固定的，所以排序后最远位置一定是A和B元素都最大的那个，依次类推，每次都找最大的那个从后向前填就可以了，代码如下：
public void merge(int[] nums1, int nums1_len, int[] nums2, int nums2_len) {
int i = nums1_len + nums2_len - 1;
int len1 = nums1_len - 1, len2 = nums2_len - 1;
while (len1 >= 0 && len2 >= 0) {
if (nums1[len1] <= nums2[len2])
nums1[i--] = nums2[len2--];
else if (nums1[len1] > nums2[len2])
nums1[i--] = nums1[len1--];
}
//假如A或者B数组还有剩余
while (len2 != -1) nums1[i--] = nums2[len2--];
while (len1 != -1) nums1[i--] = nums1[len1--];
}
void merge(int nums1[], int nums1_len, int m,int nums2[], int nums2_len,int n) {
int i = m + n - 1;
int len1 = m - 1, len2 = n - 1;
while (len1 >= 0 && len2 >= 0) {
if (nums1[len1] <= nums2[len2]) {
nums1[i--] = nums2[len2--];
} else {
nums1[i--] = nums1[len1--];
}
}
// 假如A或者B数组还有剩余
while (len2 != -1) {
nums1[i--] = nums2[len2--];
}
while (len1 != -1) {
nums1[i--] = nums1[len1--];
}
}
def merge(nums1, nums1_len, nums2, nums2_len):
i = nums1_len + nums2_len - 1
len1, len2 = nums1_len - 1, nums2_len - 1
while len1 >= 0 and len2 >= 0:
if nums1[len1] <= nums2[len2]:
nums1[i] = nums2[len2]
len2 -= 1
else:
nums1[i] = nums1[len1]
len1 -= 1
i -= 1
# 假如A或者B数组还有剩余
while len2 != -1:
nums1[i] = nums2[len2]
len2 -= 1
i -= 1
while len1 != -1:
nums1[i] = nums1[len1]
len1 -= 1
i -= 1阅读量：1176
点赞量：0
收藏量:0