Array 算法题的思考

数组类的算法是在我做的题目中是最多的,相对来说也是最好理解的它也可以包罗万象,使用各种各样的算法。用数组可以实现很多基本的数据结构。比如heap。所以这部分需要好好掌握。

SWAP

需要应用到数组元素交换是一类非常常见的题目,比如说求最大的K个数,这种题目一般都是使用基本的快速排序思想。也就是说,我们把这个数组分成两部分,一部分是比当前这个数字大的,另外一部分是比这个当前数字小的,这样我们可以快速的把一个array分成两部分,然后再分别对这两部分进行处理。

如果只是需要移动一些数字,比如说移动零或者整个数组只有三个数,那么可以用一些更简单思想,比如说记录下所有非0的数,或者记录下这些数字的个数,然后把前面全换成这些非0数,后面换成零。这样做的好处就是不需要交换。或者一个记录非0的地方,另外一个记录当前位置,如果这个不是零,那么就遇上一个非0的东西交换。所以总体思路都是双指针的思想,一个记录当前遍历的位置,另外一个记录上一次符合条件的位置。

subarray

这又是一大类数组常遇到的题目,比如说求子数组的和,或者判断这个子数组是否符合某些规律等等。与字符串处理substring有异曲同工之妙,一般也都是双指针,如果发现和大于某个值的时候,那么就把起始值增大。

另外一种常见的思路就是记录从零开始到现在的子序列的和。然后,用当前的和减去目标值,然后看这个值是否在我们存好的hashmap里,如果在的话就说明存在这么个序列,我们就可以返回这个值。这类题目需要先判断有没有,再加入map,避免0的问题。当限制subarray长度时也可以用两个数字代表,不使用hashtable。

对于求max average的题目,可以使用binary search找这个最大的average,思路不是很直接。就是直接找这个值,然后看存不存在符合的subarray.

其中一个有趣的地方是可以用加法代替乘法,换成log。

对于subarray个数的题目可以一般有这个思路:

  • 1,2 中subarray个数为[1],[2],[1,2]
  • 1,2,3 中subarray个数为[1],[2],[1,2],[1,3],[2,3],[1,2,3]

所以个数+=连续的个数。

对于数组是否排序的判断题目,重点就是弄清楚子数组最小值和最大值。如果出现小值在后,说明整块需要排序。可以从右往左看最小值,这样就可以知道这一位后面最小的值是什么。

这个是sliding window求其中的最大,可以使用一个queue存目前最大的,然后pop掉所有比这个小的,以及超出window的,只存目前最大的。queue里面放的是index。

这也是一大类型,可以用在排好序(或者满足一定关系)的数组上,也可以用来找特定的值。在rotated sorted array中找值就是可以看左右两边数字的关系,可以用来判断分界点。找范围的题目可以使用两次binary search来确定左右边界。区别就是在判断条件上不同,等号的方向不同。如果包含重复,那么就意味着存在一种全部判断数值都可能的可能性,这时候可以去减小左右端的范围。

sequence

这类题目获得的是序列,而不是连续的子数组。

  1. 有的题目在解决的时候可以无视先后顺序,可以用hashtable来思考问题。比如128,找连续的话可以首先找到最小的那个,然后往后看在不在table里。
  2. 如果还需要注意顺序的话,可以走o(n^2),一种dp思想,存这个之前比当前小的数的个数。所以每次出现新的大的数,看之前比自己小的就行。还可以可以使用binary search思考,首先有序的序列从哪里来的呢,其实可以想象一个只保存遇到的小数的序列,每次用binarysearch看新的数应该插入哪里,插在里面的话就替换原来的数,说明比这个小,插在后面的话就可以搜索的长度增加。也就是说当数字比目前已知的数大的话,搜索的范围就增大,长度加一,结果加一。所以题目的重点是在于如何构建这个有序的数组,这个数组就是可行的序列。
  3. 还有要找出所有可能sequence的题目,就是使用dfs,可以参看string那里的组合问题。看有没有sequence组成指定和的题目也是这样,可以用相同的思路。
  4. Dp 背包问题是另一种思考方式,解决序列和是否可以到一定的值。就是从大到小遍历所有可能的sum,看dp[s-num[i]]是否存在。所以是O(ns)复杂度。

sum

求和是一大问题,一般是找array里有哪些可以组成指定的值,这里主要是n sum 类型的题目,其他有一些sub array, sequence在以上的部分已经提出了。这部分其实基本是确定一点或两点,之后双指针得到最后的结果。

连续出现

这类题目一般都很简单,都是最基本的扫一遍,遇到重复的数量增加,遇到不重复的就输出,重新开始计算,需要注意最后一个的输出。感觉这是基本的word count的思路,所以反复出现。

other array question….