数据结构与算法
Last updated
Last updated
首先，将 1 亿个 IP 地址按照哈希函数的值分成 1024 个桶，每个桶里面存储的是对应哈希值的 IP 地址。然后，对于每个桶，统计出现次数最多的 IP 地址。最后，将这 1024 个桶中出现次数最多的 IP 地址进行排序，取出前三个即可。
七大排序算法的时间复杂度和稳定性如下：
| 排序算法 | 时间复杂度 | 稳定性 |
|---|---|---|
快速排序：快速排序是一种基于分治思想的高效排序算法。它的基本思想是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
归并排序：归并排序是一种基于分治思想的高效排序算法。它的基本思想是将待排元素分成大小大致相等的两个子集合，分别对这两个子集合进行递归处理，直到子集合中只有一个元素为止，然后将两个子集合合并成一个有序序列。
堆排序：堆排序是一种基于堆结构的高效排序算法。它的基本思想是将待排元素构造成一个堆，然后依次取出堆顶元素（最大或最小），再将剩余元素重新构造成一个堆，重复上述操作直到所有元素都被取出。
令牌桶算法是一种流量整形算法，它可以平滑地限制数据的传输速率。令牌桶算法的原理是系统会以一个恒定的速率往桶里放入令牌，而如果请求需要被处理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务。
红黑树和 AVL 树都是常用的平衡二叉树，它们的时间复杂度都是 O(logn)。红黑树的算法时间复杂度和 AVL 相同，但统计性能比 AVL 树更高，所以在插入和删除中所做的后期维护操作肯定会比 AVL 树要耗时好多，但是它们的查找效率都是 O(logn)
红黑树是一种自平衡的二叉搜索树，它在计算机科学中被广泛应用。它的名称来自于树中节点的颜色，每个节点要么是红色，要么是黑色。红黑树具有以下特性：
根节点是黑色的。
每个叶子节点 (NIL 节点，空节点) 都是黑色的。
如果一个节点是红色的，则它的两个子节点都是黑色的。
从任意节点到其每个叶子节点的路径上包含相同数量的黑色节点。
任意节点到其后代的所有叶子节点的简单路径上，均包含相同数量的黑色节点。
这些特性保证了红黑树的平衡性，使得它的高度始终保持在可接受的范围内。红黑树的高度是 O(logn)，其中 n 是树中节点的数量。
红黑树的自平衡性是通过在插入和删除操作后进行调整来实现的。插入和删除操作可能会破坏红黑树的特性，但通过一系列的旋转和重新着色操作，可以保持红黑树的平衡性。
红黑树在许多领域都有广泛的应用，特别是在需要高效地进行插入、删除和搜索操作的场景中。它的时间复杂度在平均和最坏情况下都是 O(log n)，使得它成为一种非常有效的数据结构。
哈希查找的时间复杂度通常被认为是 O(1)。这是因为哈希表利用哈希函数将键映射到数组的特定位置，使得对于任意给定的键，可以通过哈希函数快速计算出其对应的存储位置。在平均情况下，哈希表的搜索、插入和删除操作的时间复杂度都是 O(1)。然而，在最坏情况下，如果发生大量的哈希冲突，哈希表的性能会退化成 O(n)。
当快速排序中的枢纽元与其他元素进行交换时，可能会改变相同键值的元素的相对顺序。例如，如果有两个相同的元素 A 和 B，且 A 在 B 的前面，但在排序过程中，A 被移动到了 B 的后面，那么相同键值的元素的相对顺序就发生了改变。这就是快速排序不稳定的一个例子。
节点颜色：每个节点要么是红色，要么是黑色。
根节点颜色：根节点必须是黑色。
叶子节点颜色：叶子节点 (NIL 节点或空节点) 都是黑色。
颜色约束：红色节点的子节点必须是黑色。换句话说，不能有两个连续的红色节点。
黑高度：从根节点到任意叶子节点的路径上，经过的黑色节点数量相同。
跳表基于链表实现，通过在原始链表的基础上建立多层索引来加速查找操作。跳表的原理是通过每两个节点抽出一个节点，建立索引层，从而减少查找路径，降低查找时间复杂度。具体原理如下：
遍历有序链表时，需要从头节点开始逐个节点遍历，直到找到目标节点。这种遍历方式的时间复杂度是 O(n)。
跳表的思想是每两个节点抽出一个节点，建立第一层索引。第一层索引的节点个数是原始链表节点个数的一半。
在第一层索引的基础上，再每两个节点抽出一个节点，建立第二层索引。第二层索引的节点个数是第一层索引节点个数的一半。
以此类推，建立多层索引，直到达到某个条件（如节点个数小于等于 2）为止。
当需要查找数据时，从最高层索引开始，逐层向下查找，直到找到目标节点或者找不到为止。
在每一层索引中，通过比较节点的值，确定下一步的查找方向，可以快速缩小查找范围。
如果在某一层索引中找到目标节点，则返回该节点；如果在最底层索引中仍然找不到目标节点，则表示数据不存在。
跳表的查询时间复杂度是 O(log(n))，其中 n 是原始链表的节点个数。跳表的插入和删除操作也可以通过类似的方式进行实现，时间复杂度也是 O(log(n))。跳表的优势在于可以在不使用平衡树的情况下，实现高效的查找、插入和删除操作。
满二叉树：
每个非叶子节点都有两个子节点，且所有叶子节点都在同一层。
完全二叉树：
除了最后一层外，每层的节点数都达到最大，且最后一层的节点集中在最左边。
二叉搜索树（Binary Search Tree, BST）：
对于每个节点，左子树的所有节点值小于该节点，右子树的所有节点值大于该节点。中序遍历该树会得到一个有序序列。
平衡二叉树：
也称为 AVL 树，要求每个节点的左右子树高度差不超过 1，确保树的高度保持在对数级别，从而提高查找效率。
红黑树：
一种自平衡的二叉搜索树，每个节点有颜色属性（红或黑），并遵循特定的性质以保持树的平衡。
哈夫曼树：
一种带权路径长度最小的二叉树，通常用于数据压缩。
查询：跳表和红黑树的平均时间复杂度均为 O(logn)，但在最坏情况下，跳表的查询复杂度可能达到 O(n)，而红黑树则保持在 O(logn)。
插入和删除：跳表的插入和删除操作相对简单，通常只涉及指针的调整，时间复杂度为 O(logn)。红黑树的插入和删除则需要进行复杂的平衡调整，旋转和着色操作，因此实现较为复杂，但时间复杂度同样为 O(logn)。
跳表的空间复杂度较高，因为它需要额外的指针来维护多层结构，通常为 O(n)。相比之下，红黑树的每个节点只需要存储颜色信息和指向父节点的指针，整体上占用的内存较少。
跳表：实现较为简单，易于理解和调试，尤其适合快速开发和原型设计。跳表的结构类似于链表，插入和删除操作相对直接。
红黑树：实现复杂，需要处理多种情况以保持树的平衡，涉及旋转和颜色调整，增加了开发和维护的难度。
在并发环境下，跳表的更新操作相对较少，锁的竞争较低，因此在多线程环境中表现良好。而红黑树在并发操作时，由于其复杂的平衡调整，可能会导致更多的锁竞争。
跳表：由于其简单性和良好的性能，跳表常用于需要快速插入、删除和查找的场景，如 Redis 的有序集合（zset）实现中。
红黑树：适用于对性能要求较高且需要频繁查找的场景，如许多标准库中的集合实现，特别是在需要保持严格平衡时。
冒泡排序
O(n^2)
稳定
选择排序
O(n^2)
不稳定
插入排序
O(n^2)
稳定
希尔排序
O(nlogn)~O(n^2)
不稳定
快速排序
O(nlogn)~O(n^2)
不稳定
归并排序
O(nlogn)
稳定
堆排序
O(nlogn)
不稳定