C++ 数据结构与算法 常考面试题(一)

1. 如何实现快速排序？快排优化有哪些？

核心思想

快速排序基于分治思想，核心逻辑是：选择一个基准值，将数组划分为「小于基准」和「大于基准」的两个子数组，递归对两个子数组重复该过程，直至子数组长度为1（天然有序）。快排的性能核心取决于基准值的选择和分区效率。

代码实现（经典Hoare分区法）

#include <vector>
#include <algorithm>
using namespace std;

// 分区函数：返回基准值最终位置
int partition(vector<int>& nums, int left, int right) {
    // 选左边界为基准值
    int pivot = nums[left];
    int i = left, j = right;
    while (i < j) {
        // 右指针找小于基准的数
        while (i < j && nums[j] >= pivot) j--;
        // 左指针找大于基准的数
        while (i < j && nums[i] <= pivot) i++;
        // 交换不符合分区规则的元素
        if (i < j) swap(nums[i], nums[j]);
    }
    // 基准值归位（放到分区中间）
    swap(nums[left], nums[i]);
    return i;
}

// 快速排序主函数
void quickSort(vector<int>& nums, int left, int right) {
    // 递归终止条件：子数组长度≤1
    if (left >= right) return;
    int pivotIdx = partition(nums, left, right);
    // 递归排序左、右子数组
    quickSort(nums, left, pivotIdx - 1);
    quickSort(nums, pivotIdx + 1, right);
}

快排经典优化手段

1. 基准值优化：三数取中法（取左、中、右边界的中间值作为基准），避免有序数组导致的O(n²)最坏情况。
2. 小区间优化：当子数组长度小于10时，改用插入排序（减少递归调用的栈开销）。
3. 尾递归优化：对较长的子数组递归，较短的子数组用循环处理，降低栈帧消耗。
4. 去重优化：三路快排（将等于基准值的元素聚集到中间），避免重复元素的无效排序。

时间/空间复杂度

• 平均时间复杂度：O(nlogn)（面试必背）
• 最坏时间复杂度：O(n²)（优化后可规避）
• 空间复杂度：O(logn)（递归栈开销，最坏O(n)）

2. 如何解决二叉树的层序遍历问题？变体如何应对？

核心思想

二叉树层序遍历基于广度优先搜索（BFS），核心是利用队列记录每一层的节点，通过「记录当前层节点数」实现按层遍历，而非单纯的广度遍历。

代码实现（基础层序遍历，按行输出）

#include <vector>
#include <queue>
using namespace std;

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

// 层序遍历：返回二维数组，每行对应二叉树的一层
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;
    if (!root) return res; // 空树直接返回
    
    queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        int levelSize = q.size(); // 记录当前层的节点数
        vector<int> curLevel;
        
        // 遍历当前层所有节点
        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = q.front();
            q.pop();
            curLevel.push_back(node->val);
            
            // 子节点入队，为下一层遍历做准备
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        res.push_back(curLevel);
    }
    return res;
}

经典变体及应对技巧

时间/空间复杂度

• 时间复杂度：O(n)（每个节点仅访问一次）
• 空间复杂度：O(n)（队列最多存储一层节点，最坏为满二叉树的最后一层）

3. 如何实现哈希表？解决哈希冲突的方法有哪些？

核心思想

哈希表（散列表）的核心是通过哈希函数将键（key）映射到数组的指定索引，实现O(1)平均时间复杂度的增删改查；核心解决的问题是「哈希冲突」（不同key映射到同一索引）。

代码实现（链地址法解决冲突，工业界主流）

#include <vector>
#include <string>
#include <stdexcept>
using namespace std;

// 哈希表节点结构
template <typename K, typename V>
struct HashNode {
    K key;
    V val;
    HashNode* next;
    HashNode(K k, V v) : key(k), val(v), next(nullptr) {}
};

// 简易哈希表（链地址法）
template <typename K, typename V>
class HashMap {
private:
    vector<HashNode<K, V>*> table; // 底层数组
    int size;                       // 实际存储节点数
    const int DEFAULT_CAP = 16;     // 默认初始容量
    const float LOAD_FACTOR = 0.75; // 负载因子阈值（超过则扩容）

    // 简易哈希函数（针对int键，可扩展至其他类型）
    int hash(K key) {
        return abs((int)key) % table.size();
    }

    // 扩容：容量翻倍，重新哈希所有节点
    void resize() {
        int newCap = table.size() * 2;
        vector<HashNode<K, V>*> newTable(newCap, nullptr);
        
        for (auto& node : table) {
            HashNode<K, V>* cur = node;
            while (cur) {
                HashNode<K, V>* next = cur->next;
                int idx = abs((int)cur->key) % newCap;
                cur->next = newTable[idx];
                newTable[idx] = cur;
                cur = next;
            }
        }
        table.swap(newTable);
    }

public:
    HashMap() : table(DEFAULT_CAP, nullptr), size(0) {}

    // 插入/更新键值对
    void put(K key, V val) {
        if ((float)size / table.size() >= LOAD_FACTOR) resize();
        int idx = hash(key);
        HashNode<K, V>* cur = table[idx];
        
        // 已存在该key，更新值
        while (cur) {
            if (cur->key == key) {
                cur->val = val;
                return;
            }
            cur = cur->next;
        }
        
        // 不存在，头插法新增节点
        HashNode<K, V>* newNode = new HashNode<K, V>(key, val);
        newNode->next = table[idx];
        table[idx] = newNode;
        size++;
    }

    // 根据key查找值
    V get(K key) {
        int idx = hash(key);
        HashNode<K, V>* cur = table[idx];
        while (cur) {
            if (cur->key == key) return cur->val;
            cur = cur->next;
        }
        throw out_of_range("key not found");
    }

    // 删除指定key
    void remove(K key) {
        int idx = hash(key);
        HashNode<K, V>* cur = table[idx];
        HashNode<K, V>* pre = nullptr;
        
        while (cur) {
            if (cur->key == key) {
                if (pre) pre->next = cur->next;
                else table[idx] = cur->next;
                delete cur;
                size--;
                return;
            }
            pre = cur;
            cur = cur->next;
        }
    }

    ~HashMap() {
        // 释放所有节点内存
        for (auto& node : table) {
            HashNode<K, V>* cur = node;
            while (cur) {
                HashNode<K, V>* next = cur->next;
                delete cur;
                cur = next;
            }
        }
    }
};

解决哈希冲突的常用方法

1. 链地址法：本文实现方式，数组每个索引挂链表，冲突节点加入链表（Java HashMap、C++ unordered_map底层）。
2. 开放定址法：冲突后按规则（线性探测、二次探测）寻找下一个空位置，缺点是易产生聚集。
3. 再哈希法：冲突后用另一个哈希函数计算新索引，缺点是增加计算开销。
4. 公共溢出区法：冲突节点全部放入溢出区，适合冲突较少的场景。

4. 如何解决拓扑排序问题？Kahn 算法与 DFS 实现？

核心思想

拓扑排序针对有向无环图（DAG），核心是将图中所有节点排成一个线性序列，使得任意有向边u→v中，u都出现在v之前；常用来解决「依赖关系」问题（如课程安排、任务调度）。

方法1：Kahn算法（基于入度的BFS实现）

核心逻辑

1. 计算所有节点的入度；
2. 将入度为0的节点入队（无前置依赖）；
3. 出队节点并加入结果，将其邻接节点入度减1；
4. 重复步骤2-3，直至队空；
5. 若结果长度≠节点总数，说明图有环，无拓扑序。

#include <vector>
#include <queue>
using namespace std;

// 拓扑排序（Kahn算法）：返回拓扑序列，空数组表示有环
vector<int> topologicalSortKahn(int n, vector<vector<int>>& edges) {
    vector<int> inDegree(n, 0); // 入度数组
    vector<vector<int>> adj(n); // 邻接表
    
    // 构建邻接表+统计入度
    for (auto& edge : edges) {
        int u = edge[0], v = edge[1];
        adj[u].push_back(v);
        inDegree[v]++;
    }
    
    queue<int> q;
    // 入度为0的节点入队
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) q.push(i);
    }
    
    vector<int> res;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        res.push_back(u);
        
        // 遍历邻接节点，入度减1
        for (int v : adj[u]) {
            inDegree[v]--;
            if (inDegree[v] == 0) q.push(v);
        }
    }
    
    // 有环：结果长度≠节点数
    if (res.size() != n) return {};
    return res;
}

方法2：DFS实现（基于后序遍历）

核心逻辑

1. 递归遍历节点，标记访问状态（未访问/访问中/已访问）；
2. 访问中遇到「访问中」的节点，说明有环；
3. 后序遍历完成后，将节点加入结果；
4. 最终反转结果，得到拓扑序。

#include <vector>
#include <algorithm>
using namespace std;

// 辅助DFS函数
bool dfs(int u, vector<vector<int>>& adj, vector<int>& visited, vector<int>& res) {
    visited[u] = 1; // 标记为访问中
    for (int v : adj[u]) {
        if (visited[v] == 1) return false; // 发现环
        if (visited[v] == 0 && !dfs(v, adj, visited, res)) return false;
    }
    visited[u] = 2; // 标记为已访问
    res.push_back(u); // 后序加入结果
    return true;
}

// 拓扑排序（DFS实现）
vector<int> topologicalSortDFS(int n, vector<vector<int>>& edges) {
    vector<vector<int>> adj(n);
    for (auto& edge : edges) {
        int u = edge[0], v = edge[1];
        adj[u].push_back(v);
    }
    
    vector<int> visited(n, 0); // 0=未访问，1=访问中，2=已访问
    vector<int> res;
    
    for (int i = 0; i < n; i++) {
        if (visited[i] == 0 && !dfs(i, adj, visited, res)) {
            return {}; // 有环，返回空
        }
    }
    
    reverse(res.begin(), res.end()); // 反转后得到拓扑序
    return res;
}

两种实现对比

5. 如何实现归并排序？归并排序的应用与优化？

核心思想

归并排序基于分治思想，核心是「先分后合」：将数组拆分为两个子数组，递归排序子数组，再将有序子数组合并为一个有序数组；是稳定排序（相等元素相对位置不变）。

代码实现（经典自顶向下）

#include <vector>
using namespace std;

// 合并两个有序子数组：[left, mid] 和 [mid+1, right]
void merge(vector<int>& nums, int left, int mid, int right) {
    vector<int> temp(right - left + 1); // 临时数组存储合并结果
    int i = left, j = mid + 1, k = 0;
    
    // 合并两个有序子数组
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            temp[k++] = nums[i++];
        } else {
            temp[k++] = nums[j++];
        }
    }
    
    // 处理剩余元素
    while (i <= mid) temp[k++] = nums[i++];
    while (j <= right) temp[k++] = nums[j++];
    
    // 拷贝回原数组
    for (int p = 0; p < temp.size(); p++) {
        nums[left + p] = temp[p];
    }
}

// 归并排序主函数
void mergeSort(vector<int>& nums, int left, int right) {
    if (left >= right) return; // 递归终止条件
    int mid = left + (right - left) / 2; // 避免溢出
    // 分：递归排序左右子数组
    mergeSort(nums, left, mid);
    mergeSort(nums, mid + 1, right);
    // 合：合并有序子数组
    merge(nums, left, mid, right);
}

归并排序的优化技巧

1. 小区间优化：子数组长度<10时改用插入排序，减少递归和合并开销。
2. 原地合并：优化合并过程，避免临时数组的空间开销（实现较复杂）。
3. 自底向上迭代实现：避免递归栈开销，适合处理大数据量。
4. 提前终止：合并前检查左右子数组是否已有序，有序则直接跳过合并。

应用场景

1. 求逆序对（面试高频题，基于归并排序的合并过程统计）。
2. 外部排序（数据量超过内存时，分块排序后合并）。
3. 多路归并（如合并多个有序链表）。

时间/空间复杂度

• 时间复杂度：O(nlogn)（最好/最坏/平均均为该复杂度，稳定）。
• 空间复杂度：O(n)（临时数组开销），递归实现额外增加O(logn)栈空间。

6. 如何解决滑动窗口问题？定长与不定长窗口技巧？

核心思想

滑动窗口是双指针的经典应用，核心是用「左、右指针」维护一个动态窗口，通过移动指针调整窗口大小，在O(n)时间复杂度内解决子数组/子串问题；分为定长窗口和不定长窗口两类。

1. 定长滑动窗口（窗口大小固定）

核心技巧

1. 先扩大右指针，使窗口达到指定大小；
2. 窗口满足大小后，移动左指针保持窗口大小；
3. 遍历过程中统计窗口内的目标值。

// 示例：求长度为k的子数组的最大和
#include <vector>
#include <climits>
using namespace std;

int maxSubarraySum(vector<int>& nums, int k) {
    int n = nums.size();
    if (n < k) return 0; // 边界处理
    
    int windowSum = 0, maxSum = INT_MIN;
    int left = 0;
    
    for (int right = 0; right < n; right++) {
        windowSum += nums[right];
        
        // 窗口达到大小k
        if (right - left + 1 == k) {
            maxSum = max(maxSum, windowSum);
            // 左指针右移，保持窗口大小
            windowSum -= nums[left];
            left++;
        }
    }
    return maxSum;
}

2. 不定长滑动窗口（窗口大小动态调整）

核心技巧

1. 扩大右指针，直到窗口满足目标条件；
2. 收缩左指针，优化窗口结果，直到窗口不满足条件；
3. 遍历过程中记录最优解。

// 示例：求无重复字符的最长子串长度
#include <string>
#include <unordered_set>
using namespace std;

int lengthOfLongestSubstring(string s) {
    unordered_set<char> window;
    int left = 0, maxLen = 0;
    
    for (int right = 0; right < s.size(); right++) {
        // 有重复字符，收缩左指针
        while (window.count(s[right])) {
            window.erase(s[left]);
            left++;
        }
        // 加入当前字符，更新最大长度
        window.insert(s[right]);
        maxLen = max(maxLen, right - left + 1);
    }
    return maxLen;
}

滑动窗口解题通用步骤

1. 初始化左指针、结果变量、窗口统计变量（如和、哈希表）；
2. 右指针遍历数组/字符串，更新窗口统计变量；
3. 根据窗口类型（定长/不定长）调整左指针；
4. 遍历过程中更新结果变量。

典型应用场景

• 定长窗口：滑动平均值、长度为k的最大/最小子数组和。
• 不定长窗口：最长无重复子串、最小覆盖子串、至多包含k个不同字符的最长子串。

7. 如何实现堆排序？大顶堆 / 小顶堆的实际应用？

核心思想

堆排序基于完全二叉树的堆结构，核心是：

1. 构建大顶堆（升序排序）/小顶堆（降序排序）；
2. 交换堆顶和最后一个元素，缩小堆范围；
3. 对堆顶进行下沉调整，重复步骤2-3直至有序。

代码实现（大顶堆实现升序排序）

#include <vector>
#include <algorithm>
using namespace std;

// 下沉调整：维护大顶堆性质
void heapify(vector<int>& nums, int n, int i) {
    int largest = i; // 初始化最大元素为根
    int left = 2 * i + 1; // 左子节点
    int right = 2 * i + 2; // 右子节点
    
    // 左子节点更大
    if (left < n && nums[left] > nums[largest]) {
        largest = left;
    }
    // 右子节点更大
    if (right < n && nums[right] > nums[largest]) {
        largest = right;
    }
    
    // 最大元素不是根，交换并递归调整
    if (largest != i) {
        swap(nums[i], nums[largest]);
        heapify(nums, n, largest);
    }
}

// 堆排序主函数
void heapSort(vector<int>& nums) {
    int n = nums.size();
    // 构建大顶堆（从最后一个非叶子节点开始）
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(nums, n, i);
    }
    
    // 逐个取出堆顶元素
    for (int i = n - 1; i > 0; i--) {
        swap(nums[0], nums[i]); // 堆顶（最大）交换到末尾
        heapify(nums, i, 0); // 调整剩余元素为大顶堆
    }
}

大顶堆/小顶堆的实际应用

时间/空间复杂度

• 时间复杂度：O(nlogn)（建堆O(n)，调整堆O(nlogn)）。
• 空间复杂度：O(1)（原地排序，递归实现heapify需O(logn)栈空间）。

核心优势

• 不稳定排序，但时间复杂度稳定（最好/最坏/平均均为O(nlogn)）；
• 适合处理大数据量的TOP K问题，无需全量排序。

8. 如何解决深度优先搜索（DFS）与广度优先搜索（BFS）经典问题？

核心思想

• DFS（深度优先搜索）：优先遍历「深度」，用递归/栈实现，适合找路径、连通性、排列组合问题；
• BFS（广度优先搜索）：优先遍历「广度」，用队列实现，适合找最短路径、层序遍历、最小步数问题。

经典例题：岛屿数量（DFS实现）

#include <vector>
using namespace std;

// DFS：淹没当前岛屿（标记为已访问）
void dfs(vector<vector<char>>& grid, int i, int j) {
    int m = grid.size(), n = grid[0].size();
    // 边界/非岛屿判断
    if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') {
        return;
    }
    grid[i][j] = '0'; // 标记为已访问
    // 遍历上下左右四个方向
    dfs(grid, i - 1, j); // 上
    dfs(grid, i + 1, j); // 下
    dfs(grid, i, j - 1); // 左
    dfs(grid, i, j + 1); // 右
}

// 统计岛屿数量
int numIslandsDFS(vector<vector<char>>& grid) {
    if (grid.empty()) return 0;
    int m = grid.size(), n = grid[0].size();
    int count = 0;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '1') {
                count++;
                dfs(grid, i, j); // 淹没整个岛屿
            }
        }
    }
    return count;
}

经典例题：岛屿数量（BFS实现）

#include <vector>
#include <queue>
using namespace std;

// BFS：淹没当前岛屿
void bfs(vector<vector<char>>& grid, int i, int j) {
    int m = grid.size(), n = grid[0].size();
    queue<pair<int, int>> q;
    q.push({i, j});
    grid[i][j] = '0'; // 标记为已访问
    
    // 上下左右四个方向
    vector<pair<int, int>> dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};
    
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        
        for (auto [dx, dy] : dirs) {
            int nx = x + dx, ny = y + dy;
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == '1') {
                q.push({nx, ny});
                grid[nx][ny] = '0'; // 入队时标记，避免重复入队
            }
        }
    }
}

// 统计岛屿数量
int numIslandsBFS(vector<vector<char>>& grid) {
    if (grid.empty()) return 0;
    int m = grid.size(), n = grid[0].size();
    int count = 0;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '1') {
                count++;
                bfs(grid, i, j);
            }
        }
    }
    return count;
}

DFS vs BFS 核心对比

9. 如何实现前缀和与差分？一维 / 二维场景实战？

一、前缀和

核心思想

前缀和是预处理数组的技巧，核心是构建前缀和数组preSum，其中preSum[i]表示原数组前i个元素的和，可在O(1)时间内计算任意子数组的和。

1. 一维前缀和

#include <vector>
using namespace std;

// 构建一维前缀和数组
vector<int> buildPrefixSum(vector<int>& nums) {
    int n = nums.size();
    vector<int> preSum(n + 1, 0); // preSum[0]=0，方便计算
    for (int i = 0; i < n; i++) {
        preSum[i + 1] = preSum[i] + nums[i];
    }
    return preSum;
}

// 计算nums[left..right]的和（左闭右闭）
int getSubarraySum(vector<int>& preSum, int left, int right) {
    return preSum[right + 1] - preSum[left];
}

2. 二维前缀和

#include <vector>
using namespace std;

// 构建二维前缀和数组
vector<vector<int>> build2DPrefixSum(vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    vector<vector<int>> preSum(m + 1, vector<int>(n + 1, 0));
    
    for (int i = 0; i < m; i++) {
        int rowSum = 0;
        for (int j = 0; j < n; j++) {
            rowSum += matrix[i][j];
            preSum[i + 1][j + 1] = preSum[i][j + 1] + rowSum;
        }
    }
    return preSum;
}

// 计算子矩阵 (x1,y1) 到 (x2,y2) 的和（左闭右闭）
int getSubmatrixSum(vector<vector<int>>& preSum, int x1, int y1, int x2, int y2) {
    return preSum[x2 + 1][y2 + 1] - preSum[x1][y2 + 1] - preSum[x2 + 1][y1] + preSum[x1][y1];
}

二、差分

核心思想

差分是前缀和的逆运算，核心是构建差分数组diff，其中diff[i] = nums[i] - nums[i-1]，可在O(1)时间内对数组区间进行加减操作，最后通过前缀和恢复原数组。

1. 一维差分

#include <vector>
using namespace std;

// 构建一维差分数组
vector<int> buildDiffArray(vector<int>& nums) {
    int n = nums.size();
    vector<int> diff(n, 0);
    diff[0] = nums[0];
    for (int i = 1; i < n; i++) {
        diff[i] = nums[i] - nums[i - 1];
    }
    return diff;
}

// 对nums[left..right]的所有元素加val
void rangeAdd(vector<int>& diff, int left, int right, int val) {
    diff[left] += val;
    if (right + 1 < diff.size()) {
        diff[right + 1] -= val;
    }
}

// 从差分数组恢复原数组
vector<int> restoreArray(vector<int>& diff) {
    int n = diff.size();
    vector<int> nums(n);
    nums[0] = diff[0];
    for (int i = 1; i < n; i++) {
        nums[i] = nums[i - 1] + diff[i];
    }
    return nums;
}

• 前缀和：频繁查询子数组/子矩阵和（如leetcode 303、304题）、统计区间内满足条件的元素数。
• 差分：频繁对数组区间进行加减操作（如区间增量更新、航班预订统计）。

10. 如何解决贪心算法经典问题？贪心策略如何选择？

核心思想

贪心算法的核心是「每一步都做出局部最优的选择」，期望通过局部最优得到全局最优；关键是证明贪心策略的正确性（并非所有问题都适用贪心）。

经典例题：跳跃游戏（贪心实现）

#include <vector>
using namespace std;

// 判断是否能跳到最后一个位置
bool canJump(vector<int>& nums) {
    int n = nums.size();
    int maxReach = 0; // 记录能到达的最远位置
    
    for (int i = 0; i < n; i++) {
        if (i > maxReach) return false; // 当前位置不可达
        maxReach = max(maxReach, i + nums[i]); // 更新最远可达位置
        if (maxReach >= n - 1) return true; // 已能到达终点
    }
    return false;
}

经典例题：分发饼干（贪心策略：小饼干优先满足小胃口）

#include <vector>
#include <algorithm>
using namespace std;

// 计算最多能满足的孩子数量
int findContentChildren(vector<int>& g, vector<int>& s) {
    // 排序：孩子胃口升序，饼干尺寸升序
    sort(g.begin(), g.end());
    sort(s.begin(), s.end());
    
    int i = 0, j = 0; // i=孩子索引，j=饼干索引
    while (i < g.size() && j < s.size()) {
        if (s[j] >= g[i]) { // 饼干能满足孩子
            i++;
        }
        j++;
    }
    return i;
}

贪心策略选择技巧

1. 排序优先：多数贪心问题需先排序（如区间问题、分发问题）。
2. 局部最优导向：明确每一步的最优目标（如跳跃游戏的「最远可达」、饼干问题的「小饼干优先」）。
3. 反例验证：若能找到反例，说明贪心策略不成立（需改用DP）。

高频贪心经典问题

1. 区间调度（最多不重叠区间数）；
2. 买卖股票的最佳时机（无冷冻期）；
3. 柠檬水找零；
4. 加油站问题；
5. 划分字母区间。

时间复杂度

• 贪心算法的时间复杂度主要由排序（O(nlogn)）和遍历（O(n)）决定，整体多为O(nlogn)。