文章

数据结构算法高频总结二

发表于 更新于
作者 匆匆那年 26 分钟阅读

hash表数据很大。rehash的代价很高，怎么办

当哈希表中的数据量很大时，rehash 的代价会非常高，因为它需要分配新的存储空间并重新计算和插入所有的键值对。这种情况下，可以采用以下策略来降低或避免 rehash 的高代价：

1. 提前规划和减少 rehash

  • 1.1 预分配足够大的容量

    • 如果可以预估数据量，在初始化哈希表时就设置较大的容量（桶的数量），避免频繁 rehash。
    • 例如，在 C++ 中，std::unordered_map 支持 reserve(size_t) 方法，可以预留足够的空间。
    1
2

    std::unordered_map<int, int> map;
map.reserve(1000000); // 预分配 1,000,000 个桶

  • 1.2 降低装载因子（Load Factor）

    • 哈希表通常会根据装载因子（当前元素数量与桶数量的比值）来决定是否扩容。
    • 通过降低装载因子的阈值（如从默认的 0.75 降到 0.5），可以减少 rehash 发生的概率，但会增加内存占用。

2. 分批 rehash

分批 rehash 是一种将 rehash 的代价分摊到多次操作中的方法：

  1. 不一次性完成所有元素的迁移，而是将 rehash 分成多个小步骤。
  2. 每次插入、删除或查询操作时，只重新计算和迁移部分旧表中的元素。
  3. 使用一个辅助数据结构记录 rehash 的进度。

示例伪代码：

1
2
3

rehash_step():
    if still_elements_in_old_table:
        move_some_elements_from_old_to_new_table()

3. 使用动态哈希

动态哈希（Dynamic Hashing） 是一种适用于动态数据量的哈希表实现，避免了传统哈希表一次性扩容的代价：

  1. 线性哈希（Linear Hashing）：
    • 通过逐步扩展哈希表的大小来避免一次性扩容。
    • 每次扩展一个桶，并将旧桶的数据重新分配。
    • 适用于数据插入频繁、需要实时处理的场景。
  2. 可扩展哈希（Extendible Hashing）：
    • 使用目录（Directory）和哈希桶（Bucket）的分离设计，目录可以动态扩展。
    • 每次扩容时，仅调整对应的目录项，而不需要重新计算整个表的数据。

4. 考虑其他数据结构

如果 rehash 的代价难以接受，可以选择其他适合大规模数据存储的替代数据结构：

  • 跳表（Skip List）：
    • 一种分层的链表数据结构，支持 $O(\log n) $的查找、插入和删除操作，适合有序数据。
    • 不需要像哈希表那样频繁扩容。
  • B 树 / B+ 树：
    • 常用于数据库和文件系统，能够高效存储和查询大规模有序数据。
  • 分布式哈希表（DHT）：
    • 如果数据量特别大，可以考虑分布式存储，将数据分散到多个节点上，避免单节点 rehash 的代价。

5. 使用外存存储

当数据规模超出内存限制时，可以使用外存（磁盘）作为存储：

  • 内存 + 外存结合：
    • 在内存中保留热点数据，冷数据存储在外存中。
    • 使用缓存策略（如 LRU 缓存）管理数据。
  • 数据库支持：
    • 使用专门的数据库，如 Redis、LevelDB 等，它们内部对哈希表扩容进行了优化。

6. 使用特殊的哈希函数

如果 rehash 的主要原因是哈希冲突过多，可以优化哈希函数的选择，减少冲突，从而延长扩容周期：

  • 选择分布均匀的哈希函数，如 MurmurHash、CityHash 等。
  • 避免数据分布不均导致的过早 rehash。

7. 分片（Sharding）

将数据分片到多个独立的哈希表中，避免单一哈希表的扩容问题：

  1. 按键的某种规则（如取模运算）将数据分散到多个小哈希表。
  2. 每个小哈希表可以独立扩容，减少整体 rehash 的代价。

总结

解决大规模哈希表 rehash 高代价的问题，可以通过以下方式：

  1. 提前规划：预分配空间或降低装载因子。
  2. 分批迁移：将 rehash 操作分散到多次执行。
  3. 动态扩展：采用线性哈希或可扩展哈希等技术。
  4. 替代方案：考虑其他数据结构或分布式存储方案。

具体选择取决于应用场景的数据特点、实时性要求以及内存与性能的权衡。

二叉树前序遍历非递归

二叉树前序遍历的非递归实现，即通过使用栈（stack）来模拟递归调用的过程，按照“根-左-右”的顺序遍历二叉树。

实现思路

  1. 核心步骤：
    • 访问当前节点，将其值存入结果。
    • 如果当前节点有右子节点，将右子节点入栈（延后访问）。
    • 如果当前节点有左子节点，将左子节点入栈（优先访问）。
    • 栈为空时，遍历结束。
  2. 用栈模拟递归：
    • 前序遍历需要优先访问左子树，因此栈的顺序是先压右子节点，再压左子节点。

C++ 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

#include <iostream>
#include <stack>
#include <vector>

// 定义二叉树节点
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 非递归前序遍历
std::vector<int> preorderTraversal(TreeNode* root) {
    std::vector<int> result;
    if (root == nullptr) return result;

    std::stack<TreeNode*> nodeStack;
    nodeStack.push(root);

    while (!nodeStack.empty()) {
        TreeNode* node = nodeStack.top();
        nodeStack.pop();

        // 访问当前节点
        result.push_back(node->val);

        // 先压右子节点，再压左子节点
        if (node->right) nodeStack.push(node->right);
        if (node->left) nodeStack.push(node->left);
    }

    return result;
}

// 测试函数
int main() {
    // 创建一个简单的二叉树
    TreeNode* root = new TreeNode(1);
    root->right = new TreeNode(2);
    root->right->left = new TreeNode(3);

    std::vector<int> result = preorderTraversal(root);

    std::cout << "Preorder traversal: ";
    for (int val : result) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    // 清理内存（手动释放）
    delete root->right->left;
    delete root->right;
    delete root;

    return 0;
}

代码解析

  1. 栈的使用：
    • 使用栈保存尚未访问的节点，栈顶元素是当前要访问的节点。
    • 每次弹出栈顶节点后，将其右子节点和左子节点依次压入栈中。
  2. 遍历顺序：
    • 前序遍历顺序为“根-左-右”，通过栈的后进先出特性实现。
  3. 结果存储：
    • 每访问一个节点，将其值存入 result 数组，最终返回结果。

时间与空间复杂度

  1. 时间复杂度：$O(n)$
    • 每个节点都被访问一次，时间复杂度为线性。
  2. 空间复杂度：$O(h)$
    • 其中 $h$ 是树的高度，最坏情况下（单链表形式的树）栈中会存储$ n $个节点。

测试案例

示例输入：

1
2
3
4
5

    1
     \
      2
     /
    3

示例输出：

1

Preorder traversal: 1 2 3

总结

  • 非递归实现前序遍历的关键是用栈模拟递归调用。
  • 先压入右子节点，再压入左子节点，确保左子节点优先访问。
  • 在实际开发中，非递归实现能避免栈溢出问题，更适合处理深度较大的二叉树。

链表反转

链表反转是将链表的节点顺序颠倒的操作。下面给出链表反转的常用方法（包括单链表和双向链表的反转），以及 C++ 实现代码。

单链表反转

实现思路

  1. 使用三个指针：prev、current 和 next。
  2. 从头到尾遍历链表，每次将 current 的 next 指针指向 prev，以反转当前节点的指向。
  3. 更新 prev 和 current，直到遍历结束。
  4. 最终，prev 将指向新链表的头节点。

C++ 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

#include <iostream>

// 定义单链表节点
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 反转单链表
ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr; // 初始化前一个节点为 nullptr
    ListNode* current = head;

    while (current != nullptr) {
        ListNode* next = current->next; // 暂存下一个节点
        current->next = prev;          // 反转当前节点指向
        prev = current;                // 更新 prev 为当前节点
        current = next;                // 继续遍历下一个节点
    }

    return prev; // prev 是新的头节点
}

// 打印链表
void printList(ListNode* head) {
    while (head != nullptr) {
        std::cout << head->val << " ";
        head = head->next;
    }
    std::cout << std::endl;
}

// 测试函数
int main() {
    // 创建链表 1 -> 2 -> 3 -> 4 -> 5
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);

    std::cout << "Original list: ";
    printList(head);

    head = reverseList(head);

    std::cout << "Reversed list: ";
    printList(head);

    // 清理内存（手动释放）
    while (head != nullptr) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }

    return 0;
}

双向链表反转

实现思路

  1. 遍历双向链表，将每个节点的 next 和 prev 指针交换。
  2. 继续移动到下一个节点，直到遍历结束。
  3. 最后将尾节点作为新的头节点返回。

C++ 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

#include <iostream>

// 定义双向链表节点
struct DoublyListNode {
    int val;
    DoublyListNode* next;
    DoublyListNode* prev;
    DoublyListNode(int x) : val(x), next(nullptr), prev(nullptr) {}
};

// 反转双向链表
DoublyListNode* reverseDoublyList(DoublyListNode* head) {
    DoublyListNode* current = head;
    DoublyListNode* newHead = nullptr;

    while (current != nullptr) {
        // 交换当前节点的 next 和 prev
        std::swap(current->next, current->prev);

        // 更新新头节点
        newHead = current;

        // 移动到下一个节点（原来的 prev，现在的 next）
        current = current->prev;
    }

    return newHead;
}

// 打印双向链表
void printDoublyList(DoublyListNode* head) {
    while (head != nullptr) {
        std::cout << head->val << " ";
        head = head->next;
    }
    std::cout << std::endl;
}

// 测试函数
int main() {
    // 创建双向链表 1 <-> 2 <-> 3 <-> 4 <-> 5
    DoublyListNode* head = new DoublyListNode(1);
    head->next = new DoublyListNode(2);
    head->next->prev = head;
    head->next->next = new DoublyListNode(3);
    head->next->next->prev = head->next;
    head->next->next->next = new DoublyListNode(4);
    head->next->next->next->prev = head->next->next;
    head->next->next->next->next = new DoublyListNode(5);
    head->next->next->next->next->prev = head->next->next->next;

    std::cout << "Original doubly linked list: ";
    printDoublyList(head);

    head = reverseDoublyList(head);

    std::cout << "Reversed doubly linked list: ";
    printDoublyList(head);

    // 清理内存（手动释放）
    while (head != nullptr) {
        DoublyListNode* temp = head;
        head = head->next;
        delete temp;
    }

    return 0;
}

时间与空间复杂度

  1. 时间复杂度：

    $O(n)$

    • 每个节点只访问一次，完成反转操作。

  2. 空间复杂度：

    $O(1)$

    • 只使用常量级别的额外空间。

总结

  • 单链表反转：通过调整 next 指针，逐一反转节点的指向。
  • 双向链表反转：通过交换 next 和 prev 指针，并更新头节点。
  • 两种实现都在 $O(n)$ 时间内完成，并且只需 $O(1)$ 的额外空间。

二叉树输出每一层最右边的节点

要实现输出二叉树每一层最右边的节点，可以使用层序遍历（BFS），逐层遍历节点并记录每层的最后一个节点。以下是具体实现的思路和C++代码。

实现思路

  1. 使用队列（Queue）进行层序遍历：
    • 每次遍历时，将当前层的所有节点入队。
    • 记录当前层的最后一个节点（即遍历到当前层的最后一个节点时，保存其值）。
  2. 当队列为空时，遍历结束，结果列表中保存了每层的最右节点。

C++ 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

#include <iostream>
#include <queue>
#include <vector>

// 定义二叉树节点
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 获取二叉树每一层的最右边节点
std::vector<int> rightSideView(TreeNode* root) {
    std::vector<int> result;
    if (!root) return result;

    std::queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        int levelSize = q.size(); // 当前层的节点数量
        for (int i = 0; i < levelSize; ++i) {
            TreeNode* node = q.front();
            q.pop();

            // 如果是当前层的最后一个节点，加入结果
            if (i == levelSize - 1) {
                result.push_back(node->val);
            }

            // 将左右子节点加入队列
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }

    return result;
}

// 测试函数
int main() {
    // 创建二叉树
    //         1
    //       /   \
    //      2     3
    //       \      \
    //        5      4
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(4);

    std::vector<int> result = rightSideView(root);

    std::cout << "Right side view: ";
    for (int val : result) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    // 清理内存（手动释放）
    delete root->left->right;
    delete root->left;
    delete root->right->right;
    delete root->right;
    delete root;

    return 0;
}

代码说明

  1. 队列的使用：
    • 利用队列实现层序遍历，将每层的所有节点依次加入队列。
    • 每次处理队列时，确保记录最后一个节点的值。
  2. 层级控制：
    • 通过 levelSize 确定当前层的节点数量，确保每次只处理一层的节点。
  3. 结果存储：
    • 每次遍历到当前层的最后一个节点时，将其值存入结果列表。

时间与空间复杂度

  1. 时间复杂度：

    $O(n)$

    • 每个节点被访问一次。

  2. 空间复杂度：

    $O(n)$

    • 队列中可能同时保存最多一层的节点数，最坏情况下为树的宽度。

示例运行

输入：

1
2
3
4
5

        1
       / \
      2   3
       \    \
        5    4

输出：

1

Right side view: 1 3 4

总结

  • 本实现基于层序遍历，能够高效获取每层最右边的节点。
  • 如果需要从深度优先搜索（DFS）的角度实现，也可以通过记录节点深度的方式，但 BFS 更加直观和简单。

千万级数组如何求最大$k$个数？（用最小堆反之最大堆）千万数据范围有限，0到1000，有很多重复的，按频率排序怎么处理？

以下是针对这两个问题的解决方案，分别使用最小堆和哈希表 + 最小堆进行优化。

问题 1：千万级数组如何求最大 $k$ 个数（使用最小堆）

思路

  • 使用一个大小为 $k$ 的最小堆：
    • 将前 $k$ 个元素插入堆中，建立一个初始的最小堆。
    • 遍历剩余数组，如果当前元素比堆顶元素大，则替换堆顶元素并调整堆。
    • 遍历完成后，堆中保留的就是最大的 $k$ 个数。
  • 最小堆的特点是堆顶是堆中最小的元素，因此用于保留最大的 $k$ 个数。

C++ 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

#include <iostream>
#include <vector>
#include <queue> // 用于优先队列

std::vector<int> findTopK(const std::vector<int>& nums, int k) {
    if (nums.empty() || k <= 0) return {};

    // 定义最小堆，默认优先队列是最大堆，使用 greater<int> 改为最小堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

    // 建堆：前 k 个元素插入堆中
    for (int i = 0; i < k; ++i) {
        minHeap.push(nums[i]);
    }

    // 遍历剩余元素
    for (int i = k; i < nums.size(); ++i) {
        if (nums[i] > minHeap.top()) {
            minHeap.pop();          // 移除堆顶最小值
            minHeap.push(nums[i]);  // 插入新元素
        }
    }

    // 提取堆中元素
    std::vector<int> result;
    while (!minHeap.empty()) {
        result.push_back(minHeap.top());
        minHeap.pop();
    }
    return result;
}

// 测试函数
int main() {
    std::vector<int> nums = {3, 2, 1, 5, 6, 4, 8, 9, 10, 7};
    int k = 4;

    std::vector<int> topK = findTopK(nums, k);

    std::cout << "Top " << k << " largest numbers: ";
    for (int num : topK) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

时间复杂度

  1. 构建初始堆的时间复杂度：$O(k \log k)$。
  2. 遍历剩余 $n-k$ 个元素时，每次插入和删除操作的复杂度为 $O(\log k)$，总计 $O((n-k) \log k)$。
  3. 总时间复杂度：$O(n \log k)$。

空间复杂度

  • 最小堆的大小为 $k$，空间复杂度为 $O(k)$。

问题 2：范围 0-1000 的千万级数组，按频率排序

思路

  1. 统计频率：
    • 使用一个大小为 10011001 的数组（或哈希表）统计每个数字的出现次数。
  2. 按频率排序：
    • 使用一个最小堆（大小为 $k$，用于存储频率最高的 $k$ 个数字），或者直接将所有频率数据放入一个数组中排序。

C++ 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>

// 按频率排序
std::vector<std::pair<int, int>> sortByFrequency(const std::vector<int>& nums) {
    // 1. 统计频率
    std::unordered_map<int, int> frequencyMap;
    for (int num : nums) {
        frequencyMap[num]++;
    }

    // 2. 使用最大堆按频率排序
    auto cmp = [](const std::pair<int, int>& a, const std::pair<int, int>& b) {
        return a.second < b.second; // 按频率降序排序
    };
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, decltype(cmp)> maxHeap(cmp);

    for (const auto& entry : frequencyMap) {
        maxHeap.push(entry);
    }

    // 3. 提取结果
    std::vector<std::pair<int, int>> result;
    while (!maxHeap.empty()) {
        result.push_back(maxHeap.top());
        maxHeap.pop();
    }

    return result;
}

// 测试函数
int main() {
    std::vector<int> nums = {1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5};

    std::vector<std::pair<int, int>> sortedByFrequency = sortByFrequency(nums);

    std::cout << "Sorted by frequency (value: frequency): " << std::endl;
    for (const auto& entry : sortedByFrequency) {
        std::cout << entry.first << ": " << entry.second << std::endl;
    }

    return 0;
}

代码解析

  1. 频率统计：
    • 使用哈希表（std::unordered_map）记录每个数字的频率，时间复杂度为$O(n)$。
  2. 最大堆排序：
    • 将哈希表中的数据按频率排序，最大堆的插入和删除操作复杂度为 $O(\log k)$，总复杂度为 $O(k \log k)$。
  3. 结果输出：
    • 按频率排序的数组可以直接用于输出或进一步处理。

时间复杂度

  1. 统计频率：$O(n)$。
  2. 堆排序：$O(k \log k)$，其中 kk 是不同数字的个数（最多为 1001）。
  3. 总时间复杂度：$O(n + k \log k)$。

空间复杂度

  • 哈希表存储频率，复杂度为 $O(k)$。
  • 堆的存储复杂度为 $O(k)$。
  • 总空间复杂度：$O(k)$。

总结

  1. 最大 $k$ 个数：
    • 使用最小堆，时间复杂度为 $O(n \log k)$。
  2. 按频率排序：
    • 使用哈希表统计频率，结合最大堆排序或直接排序，时间复杂度为 $O(n + k \log k)$。

以上方法针对不同问题均优化了时间和空间复杂度，适用于处理大规模数据。

数据结构算法, 数据结构算法面经
数据结构算法 面经
本文由作者按照 CC BY 4.0 进行授权