比 O(nlog(n)) 做得更好——2.改变问题以及排序和填充数组

改变问题，以及对键进行排序和填充数组。

目录

【第1篇】比 O(nlog(n)) 做得更好——1.创造合适的条件

长按关注《Python学研大本营》，加入读者群，分享更多精彩 扫码关注《Python学研大本营》，加入读者群，分享更多精彩

比 O(nlog(n)) 做得更好——2.改变问题

哈希函数

当我在黄玉晓教授的课上了解到我们不必在字典中搜索键，而是字典使用其哈希函数立即检查内存位置以查看键是否存在时，字典成为我最喜欢的编码新事物. 我发现哈希函数的美学和功能以一种原始的方式吸引人。能够在 O(1) 时间内完成一项任务是如此强大和优雅。必须有一种方法可以利用它来发挥我的优势。该死，即使它效率不高，我也很想看看我是否可以将此功能应用于排序。

因此，在没有完全意识到的情况下，我将我的问题从排序问题转换为分组问题。

那么，第一步非常简单，我遍历未排序的数组并创建一个字典，其中字典的键是数组中的所有唯一元素，每个键的值包含有关实例数的信息给定的元素。最初，我将列表作为键的值，在找到时将键的新实例附加到其列表中，但黄教授提到，计算实例而不是将新实例附加到列表中会更有效。这一改变节省了大量时间。

使用实例列表为包含 1000 万个项目的数组创建排序字典：

使用实例的计数为包含 1000 万个项目的数组创建排序字典：

一个新问题：没有关于订单的信息

我现在有我的字典，其中包含来自未排序数组的所有唯一元素组，以及每个唯一元素的实例计数。不幸的是，我们现在遇到了在排序问题中使用字典的基本问题：字典本质上是无序的数据结构（也感谢散列函数）。我无法从字典本身中提取有关键的真实顺序的任何信息。如果没有关于键顺序的一些知识，以及在键上使用该知识的某种方式，我就无法利用字典提供的特殊功能。

这让我遇到了一个新问题——我可以在字典的键上强制一个命令吗？如果是这样，我必须找到一些方法来发现有关键顺序的知识，而不使用 keys。回到第 1 部分的结尾，我必须为我的新方法创造合适的条件。

新问题，旧方案

事实证明，我们确实有办法找到一些关于键的真实顺序的知识——而且我们非常容易得到它。如果我知道未排序数组中元素的范围，我将通过扩展知道我的字典中键的范围。根据定义，范围是按顺序排列的东西。此外，我的字典中的每个键都将落在该范围内，即使不是该范围上的每个点都有匹配的键。因此，如果我在未排序的数组中找到元素的范围，我可以使用它来将外部顺序强加到我的字典的键上。

事实证明，我不需要添加额外的步骤。我可以在创建字典的同一步骤中执行此操作。我只需要跟踪在循环未排序数组时遇到的最小值和最大值，然后 max-min+1 就是我的范围。

更新的字典创建步骤：

新条件

通过为未排序数组中的唯一元素创建字典并查找未排序数组中所有元素的范围，我现在设置了条件来解决字典键上的一个非常简单的排序问题。

https://medium.com/@ajchristian86/doing-better-than-o-nlog-n-part-2-de3c91fbe503

比 O(nlog(n)) 做得更好——3.对键进行排序和填充数组

使用范围对键进行排序

我可以使用范围对字典的键进行排序，从而允许我使用一个简单的 for 循环对它们进行排序。我遍历范围，试图在字典中找到匹配的键。如果我确实找到了匹配项，我会将该匹配项添加到一个不断增长的有序列表中。

填充每个匹配键的实例总数

如果我想使用这种方法从原始未排序数组创建一个排序数组，而不是将匹配键添加到我的有序数组中，我将每个键的实例数填充到不断增长的有序列表中。

全部一起做

整个做法是：

1.创建唯一元素及其实例的字典

1-A.查找范围

2.使用范围将每个唯一元素的实例数填充到列表中

编码如下：

并与 mergeSort 进行比较，以及验证已生成排序数组：

https://medium.com/@ajchristian86/doing-better-than-o-nlog-n-part-3-da1356f298c6

推荐书单

《Pandas1.x实例精解》

本书详细阐述了与Pandas相关的基本解决方案，主要包括Pandas基础，DataFrame基本操作，创建和保留DataFrame，开始数据分析，探索性数据分析，选择数据子集，过滤行，对齐索引，分组以进行聚合、过滤和转换，将数据重组为规整形式，组合Pandas对象，时间序列分析，使用Matplotlib、Pandas和Seaborn进行可视化，调试和测试等内容。此外，本书还提供了相应的示例、代码，以帮助读者进一步理解相关方案的实现过程。 本书适合作为高等院校计算机及相关专业的教材和教学参考书，也可作为相关开发人员的自学用书和参考手册。

链接：https://u.jd.com/UKjx4et

精彩回顾

《Pandas1.x实例精解》新书抢先看！

【第1篇】利用Pandas操作DataFrame的列与行

【第2篇】Pandas如何对DataFrame排序和统计

【第3篇】Pandas如何使用DataFrame方法链

【第4篇】Pandas如何比较缺失值以及转置方向？

【第5篇】DataFrame如何玩转多样性数据

【第6篇】如何进行探索性数据分析？

【第7篇】使用Pandas处理分类数据

【第8篇】使用Pandas处理连续数据

【第9篇】使用Pandas比较连续值和连续列

【第10篇】如何比较分类值以及使用Pandas分析库

长按关注《Python学研大本营》

长按二维码，加入Python读者群

扫码关注《Python学研大本营》，加入读者群，分享更多精彩