本章我们主要讨论当遇到一个实际的算法问题，我们应该如何解题，如何定位问题和技术选型。相关内容参考公瑾博士的《重学数据结构与算法》，公瑾老师的讲解通俗易懂，文中的方法也是多年工作的总结，希望本章能给大家提供一个通用解题的方法论。
假设我们现在面对一个实际的算法问题，则需要从以下两个方面进行思考：
即用尽可能低的时间复杂度和空间复杂度，解决问题并写出代码；
目的是更高效地解决问题。这里定位问题包含很多内容。
例如：
这个问题是什么类型（排序、查找、最优化）的问题？
这个问题的复杂度下限是多少，即最低的时间复杂度可能是多少？
采用哪些数据结构或算法思维，能把这个问题解决？
举一个具体例子（这个例子比较简单，但是能说明问题），题目如下：
在一个包含 n 个元素的无序数组 a 中，输出其最大值 max_val。
分析问题：
这个问题的类型是，在数据中基于某个条件的查找问题。
关于查找问题，我们学习过二分查找，其复杂度是 O(logn)。但可惜的是，二分查找的条件是输入数据有序，这里并不满足。这就意味着，我们很难在 O(logn) 的复杂度下解决问题。
继续分析我们会发现，某一个数字元素的值会直接影响最终结果。这是因为，假设前 n-1 个数字的最大值是 5，但最后一个数字的值是否大于 5，会直接影响最后的结果。这就意味着，这个问题不把所有的输入数据全都过一遍，是无法得到正确答案的。要把所有数据全都过一遍，这就是 O(n) 的复杂度。
所以我们可以得到初步结论：
该问题属于查找问题，所以考虑用 O(logn) 的二分查找。但因为数组无序，导致它并不适用。又因为必须把全部数据过一遍，因此考虑用 O(n) 的检索方法。这就是复杂度的下限。
当明确了复杂度的下限是 O(n) 后，你就能知道此时需要一层 for 循环去寻找最大值。那么循环的过程中，就可以实现动态维护一个最大值变量。空间复杂度是 O(1)，并不需要采用某些复杂的数据结构。代码如下：
public class FindMaxValueForArrDemo {public static void main(String[] args) {int[] arr = new int[]{4, 5, 1, 2, 3};int maxValue = findMaxValue(arr);System.out.println("最大值：" + maxValue);}private static int findMaxValue(int[] arr) {int maxValue = -1;for (int i = 0; i < arr.length; i++) {if (maxValue <= arr[i]) {maxValue = arr[i];}}return maxValue;}
}
上面的例子只是简单的热身，在面试中或者实际工作中，我们遇到的问题远比这复杂的多，所以我们需要一个通用的解题方法，下面我们来进行讨论。
面对一个未知问题时：
这个问题的时间复杂度上限是多少，也就是复杂度再高能高到哪里。这就是不计任何时间、空间损耗，采用暴力求解的方法去解题。
这个问题的时间复杂度下限是多少，也就是时间复杂度再低能低到哪里。这就是你写代码的目标。
在分析出这两个问题之后，根据问题类型设计合理的数据结构和运用合适的算法思维，从暴力求解的方法去逼近写代码的目标。
定位问题类型，问题的类型就决定了采用哪种算法思维。
经过以上分析，我们对方法论进行凝练，宏观上的步骤总结为以下 4 步：
复杂度分析。估算问题中复杂度的上限和下限。
定位问题。根据问题类型，确定采用何种算法思维。
数据操作分析。根据增、删、查和数据顺序关系去选择合适的数据结构，利用空间换取时间。
编码实现。
题目1：
在一个数组 a = [1, 3, 4, 3, 4, 1, 3]，找到出现次数最多的那个数字。如果并列存在多个，随机输出一个。
按照上面的 通用解题方法论，我们来一步一步解题。
首先我们来分析一下复杂度。假设我们采用暴力解法。利用双层循环的方式计算：
由于是双层循环，这段代码在时间方面的消耗就是 n*n 的复杂度，也就是 O(n²)。
代码如下：
private static int findMaxFreqNumber(int[] arr) {int timeMax = 0;int value = -1;for (int i = 0; i < arr.length; i++) {int timeTmp = 0;for (int j = 0; j < arr.length; j++) {if (arr[i] == arr[j]) {timeTmp++;}}if (timeMax <= timeTmp) {timeMax = timeTmp;value = arr[i];}}return value;}
接着，我们思考一下这段代码最低的复杂度可能是多少？
不难发现，这个问题的复杂度最低低不过 O(n)。这是因为某个数字的数值是完全有可能影响最终结果。例如，a = [1, 3, 4, 3, 4, 1]，随机输出 1、3、4 都可以。如果 a 中增加一个元素变成，a = [1, 3, 4, 3, 4, 1, 3, 1]，则结果为 1。
由此可见，这个问题必须至少要对全部数据遍历一次，所以复杂度再低低不过 O(n)。
显然，这个问题属于在一个数组中，根据某个条件进行查找的问题。既然复杂度低不过 O(n)，我们也不用考虑采用二分查找了。此处是用不到任何算法思维。那么如何让 O(n²) 的复杂度降低为 O(n) 呢？
答案是通过合适的数据结构，分析这个问题就可以发现，此时不需要关注数据顺序。因此，栈、队列等数据结构用到的可能性会很低。如果采用新的数据结构，增删操作肯定是少不了的。而原问题就是查找类型的问题，所以查找的动作一定是非常高频的。
在我们学过的数据结构中，查找有优势，同时不需要考虑数据顺序的只有哈希表。因此可以很自然地想到用哈希表解决问题。
哈希表（Java 中可以类比 HashMap）的结构是“key-value”的键值对，如何设计键和值呢？哈希表查找的 key，所以 key 一定存放的是被查找的内容，也就是原数组中的元素。数组元素有重复，但哈希表中 key 不能重复，因此只能用 value 来保存频次。
我们对上面的暴力解法进行修改，代码如下：
private static int findMaxFreqNumberBetter(int[] arr) {Map<Integer, Integer> map = new HashMap<>();// 存放元素和出现的次数int resValue = -1;int timeMax = 0;for (int i = 0; i < arr.length; i++) {Integer key = arr[i];if (ainsKey(key)) {map.put(key, (key) + 1);} else {map.put(key, 1);}}for (Map.Entry<Integer, Integer> entry : Set()) {int value = (Key());// 获取次数if (timeMax < value) {timeMax = value;resValue = Key();}}return resValue;}
代码调试，可以看到 HashMap 中存放的数据结构如下
传入的数组为 [1, 4, 4, 4, 1, 2, 3]
第一步 HashMap 中的数据结构如下：
第二步我们再遍历 map 中的元素，找到最大次数的元素即可。
题目：
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]来源：力扣（LeetCode）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
假设我们采用暴力解法，还是利用双层循环方法，步骤如下：
例如：第一层遍历找到 2 ，第二层只需要找打 9-2=7 的元素是否在数组中就可以了。由于是双层循环所以时间复杂度为 O(n²)。
我们再看看最低的时间复杂度是多少？
很显然，某个数字是否存在于原数组对结果是有影响的。因此，复杂度再低低不过 O(n)。
这里的问题是在数组中基于某个条件去查找数据的问题。然而可惜的是原数组并非有序，因此采用二分查找的可能性也会很低。那么如何把 O(n²) 的复杂度降低到 O(n) 呢？路径只剩下了数据结构。
在暴力的方法中，第二层循环的目的是查找 target - arr[i] 是否出现在数组中。很自然地就会联想到可能要使用哈希表。同时，这个例子中对于数据处理的顺序并不关心，栈或者队列使用的可能性也会很低。因此，不妨试试如何用哈希表去降低复杂度。
既然是要查找 target - arr[i] 是否出现过，因此哈希表的 key 自然就是 target - arr[i]。而 value 如何设计呢？这就要看一下结果了，最终要输出的是查找到的 arr[i] 和 target - arr[i] 在数组中的索引，因此 value 存放的必然是 index 的索引值。
基于上面的分析，我们就能找到解决方案，分析如下：
预期的时间复杂度是 O(n)，这就意味着编码采用一层的 for 循环，对原数组进行遍历。
数据结构需要额外设计哈希表，其中 key 是 target - arr[i]，value 是 index。这样可以支持 O(1) 时间复杂度的查找动作。
private static int[] twoSum(int[] arr, int target) {int[] res = new int[2];Map<Integer, Integer> map = new HashMap<>();// 用来存储差值和原值下标for (int i = 0; i < arr.length; i++) {map.put(target - arr[i], i);}for (int i = 0; i < arr.length; i++) {if (ainsKey(arr[i])) {// 存在差值元素int index = (arr[i]);if (i == index) {// [3,3]->6 元素重复问题continue;}res[0] = index;// 原值位置res[1] = i;// 差值位置}}return res;}
其实还可以优化几个地方，这里就不演示了，比如：
磨刀不误砍柴功
所以在碰到算法问题时，一定要对问题的复杂度进行分析，做好技术选型。这就是定位问题的过程。只有把这个过程做好，才能更好地解决问题。
常用的分析问题的方法有以下 4 种：
复杂度分析。估算问题中复杂度的上限和下限。
定位问题。根据问题类型，确定采用何种算法思维。
数据操作分析。根据增、删、查和数据顺序关系去选择合适的数据结构，利用空间换取时间。
编码实现。
本文发布于:2024-01-29 05:24:52，感谢您对本站的认可！
本文链接：https://www.4u4v.net/it/170647709513007.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
| 留言与评论（共有 0 条评论） |
