【算法与数据结构 03】数据处理的基本操作——增删查

在上一篇： 【算法与数据结构 02】选择合适的数据结构——将昂贵的“时间”转换为廉价的“空间” 中，我们学习了时空转换的思想，而它的核心就是选择合适的数据结构，将时间复杂度向空间复杂度转换。那么该如何选择合适的数据结构呢？

要想灵活使用数据结构，你需要先弄清楚数据在代码中被处理、加工的最小单位动作，也就是数据结构的基本操作，有了这些动作之后，你就可以基于此去选择更合适的数据结构了。

1. 举个栗子：代码对数据处理

例1：查找出一个数组中，出现次数最多的那个元素的数值。例如，输入数组 a = [1,6,3,5,5,5,6 ] 中，查找出现次数最多的数值。

这个例子我们在上一篇中已经分析过。使用字典的数据结构能使时间复杂度降低到O(n)，那究竟是什么让我们选择字典呢？下面仔细来聊一聊。

我们先看一下这个任务需要对数据进行哪些操作。我们在解这个题时，核心思路应该是：

• 第一步，根据原始数组计算每个元素出现的次数；
• 第二步，根据第一步的结果，找到出现次数最多的元素。

对于上面的第一步，可以提取出的基本数据操作有：

• 查找： 看能否在数据结构中查找到这个元素，也就是判断元素是否出现过。
• 新增： 针对没有出现过的情况，新增这个元素。
• 改动： 针对出现过的情况，需要对这个元素出现的次数加 1。

对于上面的第二步，可以提取出的基本数据操作有：

• 查找：访问数据结构中的每个元素，找到次数最多的元素。

由此可见，本任务会重复使用到查找。而能在 O(1) 的时间复杂度内完成查找动作的数据结构，只有字典类型。因此选择字典结构可能会比其他数据结构效率更高，事实也是如此。

注：此题解法可参考：【算法与数据结构 02】选择合适的数据结构——将昂贵的“时间”转换为廉价的“空间”

2. 数据处理的基本操作

设计合理的数据结构，要从问题本身出发，我们可以采用这样的思考顺序：

1. 分析这段代码到底对数据先后进行了哪些操作。
2. 根据分析出来的数据操作，找到合理的数据结构。

这样我们就把数据处理的基本操作梳理了出来。今后，即使你遇到更复杂的问题，无非就是这些基本操作的叠加和组合。只要按照上述的逻辑进行思考，就可以轻松设计出合理的数据结构。

数据处理的操作就是找到需要处理的数据，计算结果，再把结果保存下来。这个过程总结为以下操作：

• 找到要处理的数据。这就是按照某些条件进行查找。
• 把结果存到一个新的内存空间中。这就是在现有数据上进行新增。
• 把结果存到一个已使用的内存空间中。这需要先删除内存空间中的已有数据，再新增新的数据。

3. 方法论

经过对问题的拆解，你会发现即便是很复杂的代码，它对数据的处理也只有这 3 个基本操作，增、删、查。只要围绕这 3 个数据处理的操作进行分析，就能选择出合适的方案。总结下来，我们在思考代码优化时，可以从以下三个问题入手：

1. 这段代码对数据进行了哪些操作？
2. 这些操作中，哪个操作最影响效率，对时间复杂度的损耗最大？
3. 哪种数据结构最能帮助你提高数据操作的使用效率？

对于前面两个问题，围绕数据处理的基本操作，这可以通过刷题加深我们的理解。对于第3个问题，就需要我们去掌握相应的数据结构基础知识，这个我在后面也会逐渐整理出来。

参考链接：https://kaiwu.lagou.com/course/courseInfo.htm?courseId=185#/detail/pc?id=3341

文章来源: ai-wx.blog.csdn.net，作者：AI 菌，版权归原作者所有，如需转载，请联系作者。

原文链接：ai-wx.blog.csdn.net/article/details/106490810