数组题目介绍

数组是最基本的数据结构,题目设计范围广泛,可以是操作原数组、查找、排序等,也可以和贪心算法、动态规划、递归、二分法等算法结合,还可以和哈希表、二叉树等数据结构结合。本篇总结主要介绍直接在数组上操作的题目。

问题类型与技巧

  1. 数组的变型操作:可以是数组元素中的旋转、交换、移动。

    这类题型比较多,最重要的方法是找规律,不管是一维数组还是二维数组,观察变化后的数组与原数组的差异,思考如何最方便的变换。常用的技巧可能有:翻转使用双指针交换、旋转可能会用到多次翻转、矩阵可能与转置有关、另外开辟一个数组空间来存储中间值或者结果值等。

  2. 根据数组的下标,构造原地哈希。

    如果数组中的元素与下标有关系,则可以构造根据下标当成值的索引,快速找到某个值。

  3. 数组的遍历问题。

    一维数组的遍历比较常规与简单,主要是二维数组可能会有不同的遍历方式,这种情况下多模拟,画图遍历几次,就知道大概怎么遍历。

经典题型

  • 题目①螺旋矩阵

    这道题目主要是上述问题第三点,属于数组遍历的问题。题目是一个二维数组,因此可以通过画图模拟过程,再根据过程写代码。 alt

  • 题目②顺时针旋转矩阵

    这道题目主要是上述问题第一点,二维数组的旋转变型。二维数组比较抽象,可以画出如下图,发现变换与转置和逐行翻转有关系,而矩阵的转置就是遍历下三角矩阵,将其与上三角(下标互换)矩阵的元素交换位置。 alt alt

  • 题目③旋转数组

    数组上面的变型操作,一半而言都可以使用另一个数组空间来承接变换,但是如果要求在原数组上修改的话,优先考虑翻转或者分段翻转,或者局部交换位置。这道题就是经过了三次不同位置的翻转达到了旋转数组的效果。 alt

  • 题目④缺失的第一个正整数

    这道题目是上述问题第二点,可以通过构造原地哈希实现。因为题目的1~n与数组下标0~n-1刚好一一对应,可以使用下标指向某一个出现的数字。 alt

  • 题目⑤调整数组顺序使奇数位于偶数前面

    这道题也是对应上述问题第一点,变换数组。在原数组上不便于操作,我们可以构造一个新数组,承接变换后的结果,这样相当于直接赋值。 alt