2017-02-02

编程之法读书笔记第一章——数据结构——数组

导读写得比正文正经多了

《编程之法：面试和算法心得》

第一部分 数据结构

第二章 数组

笔试和面试中，除了字符串，另一类出现频率极高的问题便是与数组相关的问题。在阅读完第 1 章和本第二章后，读者会慢慢了解到解决面试编程题的有几种常用思路。首先一般考虑 “万能的” 暴力穷举（递归、回溯），如求 n 个数的全排列或八皇后（N 皇后问题）。但因为穷举时间复杂度通常过高，所以需要考虑更好的方法，如分治法（通过分而治之，然后归并），以及空间换时间（如活用哈希表）。
此外，选择合适的数据结构可以显著提升效率，如寻找最小的 k 个数中，用堆代替数组。
再有，如果题目允许排序，则可以考虑排序。比如，寻找和为定值的两个数中，先排序，然后用前后两个指针往中间扫。而如果如果已经排好序了（如杨氏矩阵查找中），则想想有无必要二分。但是，如果题目不允许排序呢？这个时候，我们可以考虑不改变数列顺序的贪心算法（如最小生成树 Prim、Kruskal 及最短路 dijkstra），或动态规划（如 01 背包问题，每一步都在决策）。
最后，注意细节处理，不要忽略边界条件，如字符串转换成整数。

2.1 寻找最小的 k 个数

排序,然后遍历

O（n log n)+O(k)=O（n log n）

选择或交换排序

1、遍历 n 个数，把最先遍历到的 k 个数存入到大小为 k 的数组中，假设它们即是最小的 k 个数；

2、对这 k 个数，利用选择或交换排序找到这 k 个元素中的最大值 kmax（找最大值需要遍历这 k 个数，时间复杂度为 O（k））；

3、继续遍历剩余 n-k 个数。假设每一次遍历到的新的元素的值为 x，把 x 与 kmax 比较：如果 x < kmax ，用 x 替换 kmax，并回到第二步重新找出 k 个元素的数组中最大元素 kmax‘；如果 x >= kmax ，则继续遍历不更新数组。

每次遍历，更新或不更新数组的所用的时间为 O（k） 或 O（0） 。故整趟下来，时间复杂度为 n O（k）=O（nk）

我其实没懂

2.2 寻找和为定值的两个数

穷举 O(N^2)

解法总结

1、二分（若无序，先排序后二分），时间复杂度总为 O(N log N)，空间复杂度为 O（1）；
2、扫描一遍 X-S[i] 映射到一个数组或构造 hash 表，时间复杂度为 O(N)，空间复杂度为 O(N)；
3、两个指针两端扫描（若无序，先排序后扫描），时间复杂度最后为：有序 O(N)，无序 O(N log N + N)=O(N log N)，空间复杂度都为 O(1)。

2.4 最大连续子数组和

暴力解法

我其实连三层循环都没看懂

int MaxSubArray(int* A, int n)
{
    int maxSum = a[0];  //全负情况，返回最大负数
    int currSum = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = i; j < n; j++)
        {
            for (int k = i; k <= j; k++)
            {
                currSum += A[k];
            }
            if (currSum > maxSum)
                maxSum = currSum;

            currSum = 0; //这里要记得清零，否则的话sum最终存放的是所有子数组的和。
        }
    }
    return maxSum;
}

太tm难了我受不了了…

算法