总结了常见数组题目的类型,包括数组的遍历、统计数组中的元素、数组的改变等,每一种类型都有一些典型的例题,有些做了方法的整理、罗列、总结,有些只是陈列,充当相似题目以便于练手。
数组的遍历
628. 三个数的最大乘积
给你一个整型数组 nums
,在数组中找出由三个数组成的最大乘积,并输出这个乘积。
思路:这里用的方法很讨巧,我们在给数组排序后,分别求出三个最大正数的乘积,以及两个最小负数与最大正数的乘积,二者之间的最大值即为所求答案。若想减少时间复杂度,只要求出数组中最大的三个数以及最小的两个数,因此我们可以不用排序,用线性扫描直接得出这五个数。
代码如下:
1 | int maximumProduct(vector<int>& nums) { |
总结:在目标问题只有几种可能结果时,囫囵着求解,最后比较结果,不失为一种省力又讨好的方法。
统计数组中的元素
645. 错误的集合
集合 s 包含从 1 到 n 的整数。不幸的是,因为数据错误,导致集合里面某一个数字复制了成了集合里面的另外一个数字的值,导致集合 丢失了一个数字 并且 有一个数字重复 。给定一个数组 nums
代表了集合 S
发生错误后的结果。请你找出重复出现的整数,再找到丢失的整数,将它们以数组的形式返回。
697. 数组的度
448. 找到所有数组中消失的数字
442. 数组中重复的数据
41. 缺失的第一个正数
(难想到,但是同样利用数组的索引作为切入点,与下方的总结是同样的思想)
总结:如何统计元素有没有出现,或者有没有重复出现?
我们可以直接统计元素出现的次数。当然,有些题目需要我们只能额外使用常数空间复杂度来解题。那我们这时候可以仔细读题,观察额外条件,例如每个数都是在[1,n]范围内的,那说明每个数都是正数,而且原数组和我们想用的cnt数组的长度时相同的,我们可以想办法修改原数组,使得原数组包含每个数是否出现的信息,比如在遍历至nums[i]时,使nums[nums[i]-1]变为负数,因为nums[i]原来是大于0的,所以在遍历完数组后,nums[i]小于0,说明i+1这个数出现过;或者原先的数都是小于数组长度的,可以使满足条件的对应位的值加上长度值作为标记。
数组的改变、移动
453. 最小操作次数使数组元素相等
给定一个长度为 n 的 非空 整数数组,每次操作将会使 n - 1 个元素增加 1。找出让数组所有元素相等的最小操作次数。//还没有在有效时间内完成任务!
方法一 动态规划
简而言之,我们对数列进行排序,一直更新 moves
以使得直到当前的元素相等,而不改变除了当前元素之外的元素。在整个数组扫描完毕后,moves
即为答案。
方法二 数学法
将除了一个元素之外的全部元素+1,等价于将该元素-1,因为我们只对元素的相对大小感兴趣。因此,该问题简化为需要进行的减法次数。显然,我们只需要将所有的数都减到最小的数即可。//特别妙!
665. 非递减数列
- 二维数组及滚动数组
一些想法:在二维数组中,每个元素都是一个一维数组。有的时候,二维数组的某些元素并不是在整个运算过程中都要用到的。可能只需要用到前一个或前两个一维数组,此时,我们可以用到滚动数组。在滚动数组中,我们用若干个(k)一维数组保存原二维数组中的倒数k个一维数组,并在运算过程中更新这k个一维数组。
数组的旋转
189. 旋转数组
给定一个数组,将数组中的元素向右移动 k
个位置,其中 k
是非负数。
方法一 环状替换
可以将被替换的元素保存在变量 \textit{temp}temp 中,从而避免了额外数组的开销。
方法二 数组翻转
我们可以先将所有元素翻转,这样尾部的 k\bmod nkmodn 个元素就被移至数组头部,然后我们再翻转 [0, kmod n-1][0,kmodn−1] 区间的元素和 [k mod n, n-1][kmodn,n−1] 区间的元素即能得到最后的答案。
396. 旋转函数
特定顺序遍历二维数组
54. 螺旋矩阵
调整方向时可利用取余!
if (nextRow < 0 || nextRow >= n || nextColumn < 0 || nextColumn >= n || matrix[nextRow][nextColumn] != 0) {
directionIndex = (directionIndex + 1) % 4; // 顺时针旋转至下一个方向}
396. 旋转函数
498. 对角线遍历
二维数组变换
566. 重塑矩阵
二维数组的一维表示
对于 x \in [0, mn)x∈[0,mn),第 xx 个元素在 \textit{nums}nums 中对应的下标为 (x / n, x% n)(x / n,x % n),而在新的重塑矩阵中对应的下标为 (x / c, x% c)(x / c,x % c)。
48. 旋转图像
就是利用环状替换,旋转时对应的坐标不要搞错。
289. 生命游戏
前缀和数组
303. 区域和检索 - 数组不可变
304. 二维区域和检索 - 矩阵不可变
思路:求区域内的和,可先求前缀和,再用两个前缀和做减法,这样就能“一次计算,终生受益”。
238. 除自身以外数组的乘积
给你一个长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
思路:使用前缀和以及后缀和相乘得到结果,为时间常数空间复杂度,要尽可能利用已有的空间大小,如要输出的结果数组的空间。
本文链接: http://example.com/2021/06/13/leetcode%E5%88%B7%E9%A2%98%E2%80%94%E6%95%B0%E7%BB%84%E7%AF%87/
版权声明: 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!