【算法】数组就是这么简单总结篇

一、背景

之前介绍了数组就是这么简单的相关话题。
如《数组就是这么简单》、《二维数组就是这么简单》、《字符串就是这么简单》、《双指针就是这么简单》。
现在对数组整体回顾一下。

二、相关技术

基于数组实现的数据结构特别多，比如字符串、哈希表、链表、队列与栈。
而数组上的经典算法也很多，如排序算法、二分查找、双指针（快慢指针 & 滑动窗口）等等。

这些都是很基础的数据结构和算法思想，大家还是要多多练习与实际运用才能真正掌握。
知道这个思想 与 能够使用这种思想 解决问题是 不一样的，一个是理论知识，一个是实践应用。
最典型的是DP思想（动态规划）,很多人知道，但是做题的时候每次换个马甲就不认识了。

下面来简单看几个有代表性的题目吧。

三、旋转数组

题意：给一个数组，将数组中的元素循环向右移动 k 次。
要求：使用O(1)的空间复杂度，至少三个方法。

思路：首先有一个优化的地方：如果k大于数组大小的话，可以取模一下。

方法一：按题意，依序循环移动即可。
时间复杂度：O(n*k)。
算法评价：这个方法复杂度较高，很容易超时。

方法二：简单分析数组后，发现一次可以移动一个连续的块，这样就可以加速移动了。

如图：当k小于左半部时，相当于最右边连续k个数字不断向左移，移到尽头尽头就是答案。
而我们每次可以移动k个，这样就相当于是和相邻的等长数组进行交换，一层循环即可。
对于k大于左半部时，可以将左半部向右移，其逻辑与左移完全等价。
复杂度：O(n)
算法评价：这个时间复杂度已经是最优的了，但是实现较为复杂。

方法三：我们的目标是将两个不等长的连续数组进行交换。
如果先对这个数组进行反转的话，我们会发现两个连续数组已经交换了位置，只是顺序反了。
因此再分别对两个数组反转即可得到答案。
复杂度：O(n)
算法评价：在保持时间复杂度最优的情况下，能够适应较为简单的代码实现，挺不错的。

四、杨辉三角 II

题意：给一个k，求杨辉三角的第k行数字。
要求：空间复杂度要求只用O(K)。

思路：由于不能使用二维数组，这里只能使用在原数组上滚动计算了。
滚动计算有一个原则：更新一个位置之后，这个位置之后再也不会使用了。

0: 1
1: 1 1
2: 1 2 1
3: 1 3 3 1
4: 1 4 6 4 1

方法一：简单分析，可以发现，从后到前计算即可，而且公式是s[i] += s[i-1]
复杂度：O(n^2)
算法评价：在较高的复杂度下，较为简洁的实现了代码。

方法二：其实，杨辉三角对应的几何意义是组合数，即C(n, k)。
所以我们直接计算组合数即可。
根据一个公式我们可以一层循环计算来。

  C(n,k) 
= A(n, k)/k! 
= A(n, k-1) * (n - k + 1)/((k-1)! * k) 
= A(n,k-1)/(k-1)! * (n-k+1)/k
= C(n, k-1) * (n - k + 1)/k  

复杂度：O(n)
算法评价：利用组合的理论，在最优的时间内计算出了答案。

五、反转字符串中的单词 III

题意：给你一个字符串，翻转所有单词。
思路：找到每个单词的边界，翻转即可。
复杂度：O(n)

六、删除排序数组中的重复项

题意：给一个有序数组，删除数组中的重复数据。
要求：使用O(1)的空间复杂度。
思路：前面的文章介绍过快慢指针，使用这个思想一层循环即可完成操作。
复杂度：空间复杂度O(n)

七、翻转字符串里的单词

题意：给一个字符串，按照单词对字符串进行反转。
例如the sky is blue反转后，得到blue is sky the。
要求：反转后，删除前后缀的空格，中间的空格有多个时，保留一个。

思路：在循环移动字符串的题中，我们已经做过了交换两个连续数组的题型。
现在这个相当于交换多个连续数组，但是思想是一样的，都是double swap。
即先对每个单词单独反转，然后对整个字符串翻转，即可得到答案。
复杂度：O(n)
算法评价：利用double swap思想，较为简洁的实现了代码（查找空格可以使用find函数的）。

注意：这里删除空格时，使用了临时的string，如果使用之前讲解的快慢指针，可以不申请额外空间的情况下完成删除空格。

八、移动零

题意：给一个数组，将所有的0移动到最后，其他数字顺序保持不变。
分析：依旧是快慢指针的练习题。
复杂度：O(n)

九、最后

数组上的练习题差不多就讲解完了。
其实常见的题型也就几种：快慢指针（删除某些值）、翻转字符串、翻转局部字符串等。
接下来就是分享栈和队列这个数据结构了。

-EOF-