算 法 笔 记

力扣

两个栈实现先进先出队列

class MyQueue{ private: stack<int>inStack,outStack; void in2out(){//in栈元素全部移动到out栈中 while (!inStack.empty()) { outStack.push(inStack.top()); inStack.pop(); } } public: MyQueue() { } void push(int x) {//入队 inStack.push(x); } int pop() {//出队并返回队首元素 if (outStack.empty()) in2out(); int x = outStack.top(); outStack.pop(); return x; } int peek() {//返回队首元素 if (outStack.empty()) in2out(); return outStack.top(); } bool empty() { return inStack.empty() && outStack.empty(); } };

//out栈空才可调用in2out函数

用两个队列实现栈

class MyStack { private: queue<int>q; public: MyStack() { } void push(int x) { q.push(x); for (int i = 1; i < q.size(); i++) {//关键函数 q.push(q.front()); q.pop(); } } int pop() { int x = q.front(); q.pop(); return x; } int top() { return q.front(); } bool empty() { return q.empty(); } };

最小栈

定义两个栈 原数栈data 最小栈min

>输入x

1> 当x<=min.top() min压x

2> 当x>min.top() min压min.top();

>输出

输出data.top(),min data 同时出栈

洛谷

1>Abcd!--ABCD!

cin.ignore();

int main() { string s; getline(cin, s); for (int i = 0; i < s.size(); i++) if (s[i] >= 'a' && s[i] <= 'z') s[i] -= 32; cout << s; return 0; }

65（A）~ 90（Z）

97（a）~ 122（z）

'a'-'A'=32

tips:

1>log以二为底N常写为logN

2>.size() .length() 计算字符串长度//。.length（）部分场景不能用。

#include<string> int main() { string a = "abcdefg"; cout << a.size(); return 0; }

3>eg:L-R,求中间值

mid=L+R=L+(R-L)/2=L+(R-L)>>1；//防止数值溢出，位运算快于算术运算

4>vector二维数组

// 定义 n 行 m 列的二维数组，所有元素默认值为 0 vector<vector<int>> arr(n, vector<int>(m)); // 定义 n 行 m 列的二维数组，所有元素初始值为 x（比如 x=5） vector<vector<int>> arr(n, vector<int>(m, x));

5>数组元素量

int arr[] = { 1,2,3,4,5 }; int num = sizeof(arr) / sizeof(int);=>sizeof(arr) / sizeof(arr[0]); / sizeof(int);//num=5

6>for (int num : arr)

7>隐式转换

\

8>常用极限值

INT_MAX int类型的最大值 <limits.h>

移动运算？位运算？

时间复杂度

递归

eg:阶乘

int J(int i) { if (i == 1) return 1;//不返回函数自身即为终止 return i * J(i - 1); } int main() { int i; cin >> i; cout << J(i); return 0; }

二分查找

int find(int arr[], int target)//返回下标 { int len = sizeof(arr) / sizeof(int); int left = 0; int right = len + 1; while (left <= right) {//查找范围非空 int mid = left + (right - left) / 2;//避免溢出 if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1;//未找到返回-1 }

memset

void *memset(void *ptr, int value, size_t num);

• ptr：要初始化的内存块起始地址（数组名、指针等）；
• value：要填充的「字节值」（只能是 0~255 的整数，超出范围会截断为字节）；
• num：要填充的「字节数」（不是元素个数！）；
• 适用：静态数组、字符数组、标记数组初始化；
• 避坑：不用于非 0/-1 数值、不用于 vector、需连续内存。

int a[5] = { 1 }; memset(a, 0, sizeof(a));//初始化为0

异或运算

异或运算（XOR）是编程中常用的位运算，符号为^（C++ 中），核心规则是：两个二进制位相同则结果为 0，不同则结果为 1。

一、异或运算的基础规则

异或运算针对两个数的每一位二进制位单独计算，规则简单：

通俗记忆：「相同为 0，不同为 1」，也可以理解为「无进位加法」（只加不进位）。

示例（十进制转二进制计算）：

• 3（二进制011）^ 5（二进制101）=110（十进制 6）
• 6（110）^ 6（110）=000（十进制 0）
• 0（000）^ 8（1000）=1000（十进制 8）

二、异或运算的核心性质（实用！）

异或的这些性质是编程中的「解题技巧」，尤其适合去重、判等、交换变量等场景：

1. 自反性：a ^ a = 0（一个数和自己异或，结果必为 0）
2. 零元性：a ^ 0 = a（一个数和 0 异或，结果还是自己）
3. 交换律：a ^ b = b ^ a（交换顺序，结果不变）
4. 结合律：(a ^ b) ^ c = a ^ (b ^ c)（先算哪部分，结果不变）
5. 判等性：a == b等价于(a ^ b) == 0（两个数相等 → 异或结果为 0，反之亦然）

三、C++ 中的异或运算应用

1. 最基础：判断两个数是否相等（替换==）

结合性质 5，异或可以替代==判断两个数是否相等，尤其在位运算优化中常用。

// 原来的写法：直接用 == if (a[i][j] == J[k]) { ... } // 异或等价写法：结果为 0 则相等 if ((a[i][j] ^ J[k]) == 0) { ... }

两者功能完全一致，只是异或更偏向「位级操作」，在某些场景（如底层优化）更高效。

2. 交换两个变量（无需临时变量）

传统交换变量需要临时变量temp，而异或利用「自反性 + 零元性」，可以无临时变量交换：

int x = 3, y = 5; x = x ^ y; // x = 3^5 = 6 y = x ^ y; // y = 6^5 = 3（等价于 (3^5)^5 = 3^(5^5) = 3^0 = 3） x = x ^ y; // x = 6^3 = 5（等价于 (3^5)^3 = 5^(3^3) = 5^0 = 5） cout << x << " " << y; // 输出 5 3

数组中a[i],a[j]也可互换//i,j不相等

3. 找数组中「唯一出现奇数次的数」

如果数组中只有一个数出现 1 次，其他数都出现 2 次，利用a^a=0和a^0=a，可以快速找到这个数：

int arr[] = {2, 4, 3, 4, 2}; int unique = 0; for (int num : arr) { unique ^= num; // 等价于 unique = unique ^ num } cout << unique; // 输出 3（只有 3 出现 1 次）

原理：2^4^3^4^2 = (2^2) ^ (4^4) ^ 3 = 0^0^3 = 3。

3. 找数组中「出现奇数次的数」

#include <iostream> #include <vector> using namespace std; void printOddTimesNum2(vector<int>& arr) { int eor = 0; // 步骤1：计算所有数的异或和（eor = a ^ b） for (int num : arr) { eor ^= num; } // 步骤2：提取 eor 最右侧的 1（rightOne） int rightOne = eor & (~eor + 1);//&联想条件判断 int onlyOne = 0; // 步骤3：分组异或，拆分出其中一个奇数次的数 for (int cur : arr) { if ((cur & rightOne) != 0) { // 按 rightOne 位分组 onlyOne ^= cur; } } // 另一个奇数次的数 = eor ^ onlyOne cout << onlyOne << " " << (eor ^ onlyOne) << endl; } int main() { vector<int> arr = {1, 2, 3, 2, 1, 4}; // 测试用例：3和4出现奇数次 printOddTimesNum2(arr); return 0; }

0 1 1 0 （eor） & 1 0 1 0 （~eor + 1） --------- 0 0 1 0 （结果）

高精度

//用数组模拟手工运算

//eg:洛谷p1009

#include <iostream> #include <vector> #include <algorithm> using namespace std; // 高精度乘法：vector<int>（低位在前） × 整数b vector<int> multiply(vector<int> a, int b) { vector<int> res; int carry = 0; // 进位 for (int i = 0; i < a.size() || carry; ++i) { if (i < a.size()) carry += a[i] * b; res.push_back(carry % 10); // 存储当前位 carry /= 10; // 更新进位 } return res; } // 高精度加法：vector<int>（低位在前） + vector<int>（低位在前） vector<int> add(vector<int> a, vector<int> b) { vector<int> res; int carry = 0; // 进位 for (int i = 0; i < a.size() || i < b.size() || carry; ++i) { if (i < a.size()) carry += a[i]; if (i < b.size()) carry += b[i]; res.push_back(carry % 10); // 存储当前位 carry /= 10; // 更新进位 } return res; } int main() { int n; cin >> n; vector<int> sum = {0}; // 存储总和，初始为0（低位在前） vector<int> fact = {1}; // 存储当前阶乘，初始为1! = 1（低位在前） for (int k = 1; k <= n; ++k) { fact = multiply(fact, k); // 计算k! = (k-1)! × k sum = add(sum, fact); // 累加阶乘和 } // 逆序输出结果（因为存储是低位在前） for (int i = sum.size() - 1; i >= 0; --i) { cout << sum[i]; } cout << endl; return 0; }

>>高精度计算原理

高精度计算的核心是用数组模拟手工运算，将大数字的每一位单独存储（通常低位在前，方便处理进位），然后模拟乘法、加法的进位逻辑。

高精度加

int main() { string s1, s2; int a1[200] = { 0 }, a2[200] = { 0 }, a3[200] = {0}; cin >> s1 >> s2; for (int i = 0; i < s1.size(); i++) a1[i] = s1[s1.size() - 1 - i] - '0';//s1倒序输入a1 for (int i = 0; i < s2.size(); i++) a2[i] = s2[s2.size() - 1 - i] - '0';//s2倒序输入a2 int len = s1.size(); if (len < s2.size()) len = s2.size();//找出s1,s2最大长度 for (int i = 0; i < len; i++) {//a1,a2各元素相加得a3 a3[i] = a1[i] + a2[i]; } for (int i = 0; i < len; i++) {//处理a3数据，满10进1 if (a3[i] >=10) { a3[i + 1] += 1; a3[i] = a3[i] % 10; } } if (a3[len] != 0) len++; for (int i = len - 1; i >= 0; i--) cout << a3[i]; return 0; }

高精度减

int main() { string s1, s2; int a1[200] = { 0 }, a2[200] = { 0 }, a3[200] = { 0 }; cin >> s1 >> s2; char flag = '+'; if (s1.size() < s2.size() || s1.size() < s2.size() && s1 < s2) {//转换s1为较大的 string r = s1; s1 = s2; s2 = r; flag = '-'; } for (int i = 0; i < s1.size(); i++) a1[i] = s1[s1.size() - 1 - i] - '0';//s1倒序输入a1 for (int i = 0; i < s2.size(); i++) a2[i] = s2[s2.size() - 1 - i] - '0';//s2倒序输入a2 int index = 0; for (int i = 0; i <s1.size(); i++) { if (a1[i] < a2[i]) { a1[i] = a1[i] + 10; a1[i + 1] -= 1; } a3[i] = a1[i] - a2[i]; if (flag == '-') cout <<"-"; for (int j = s1.size() - 1; j >= 0; j--) { if (a3[i] != 0) index = i; } } for (int i = index; i >= 0; i--) cout << a3[i]; return 0; }

高精度乘

//高精度数*单精度数 高精度数*高精度数

高精度数*单精度数

int main() { string s; int a[200] = { 0 }; int b = 0; cin >> s >> b; for (int i = 0; i < s.size(); i++) { a[i] = s[s.size() - 1 - i] - '0'; } for (int i = 0; i < s.size(); i++) a[i] *= b; for (int i = 0; i < s.size() + 4; i++) {//此处4考虑b的取值，b<=10000; if (a[i] >= 10) { a[i + 1] += a[i] / 10; a[i] %= 10; } } int index = 0; for (int i = s.size() + 4 - 1; i >= 0; i--) { if (a[i] != 0) { index = i; break; } } for (int i = index; i >= 0; i--) cout << a[i]; return 0; }

高精度数*高精度数

高精度除

单精度/单精度=x.xxx......

int main() { int a = 0;//被除数 int b = 0;//除数 int n = 0;//小数点后保留位数 cin >> a >> b >> n; cout << a / b << '.'; int t = a % b;//初始化为余数 for (int i = 0; i < n; i++) { t = t * 10; cout << t / b; t = t % b; } return 0; }

高精度/单精度=x......余数

string s; int a[Max] = { 0 };//被除数 int b = 0;//除数 int c[Max] = { 0 };//结果 cin >> s>>b; for (int i = 0; i < s.size(); i++)a[i] = s[i] - '0'; int t = 0;//余数 for (int i = 0; i < s.size(); i++) { t = t * 10 + a[i]; if (t >= b) { c[i] = t / b; t = t % b; } else c[i] = 0; } int index = 0; for (int i = 0; i < s.size(); i++) { if (c[i] != 0) { index = i; break; } } for (int i = index; i < s.size(); i++)cout << c[i]; cout << "......";

高精度/高进度=x......余数

对比器/对数器

>验证算法正确性的工具，比对欲测算法与正确算法

组成：

1. 随机数组生成器：生成大量随机测试数据（数组长度、元素值可自定义）；
2. 标准正确算法：用系统 / 公认正确的算法（如 C++ 标准库sort）作为 “参照物”；
3. 待验证算法：你自己写的算法（如之前的插入排序）；
4. 结果对比器：对比两个算法的输出结果，判断是否一致。

排序

排序稳定性

>本质：相同值在排序后前后顺序不变
排序稳定性指相同关键字元素排序后相对位置保持不变，核心影响多字段排序场景（如先按成绩排序、再按姓名排序需保留成绩排序结果）。
>稳定排序：冒泡排序、插入排序、归并排序，例：[2(甲),2(乙)]排序后仍为[2(甲),2(乙)]。
>不稳定排序：快速排序、选择排序、希尔排序，例：[2(甲),2(乙)]可能变为[2(乙),2(甲)]。

冒泡排序

选择排序

插入排序//O（N^2）

void swap(int arr[], int i, int j) { arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; } int main() { int arr[] = { 9,5,1,6,2,3,8,4,7 };//1-9 int len = sizeof(arr) / sizeof(int); for (int i = 1; i < len; i++) { for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) { swap(arr, j, j+1); } } for (int i = 0; i < len; i++) { cout << arr[i]; } return 0; }

快速排序

归并排序

O(n log n)

// 合并两个有序子数组 void merge(vector<int>& arr, int L, int M, int R) { vector<int> temp(R - L + 1); int p1 = L, p2 = M + 1; int i = 0; while (p1 <= M && p2 <= R) { temp[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++]; } while (p1 <= M) temp[i++] = arr[p1++]; while (p2 <= R) temp[i++] = arr[p2++]; for (i=0; i < temp.size(); i++) arr[L + i] = temp[i]; } // 归并排序（递归拆分+合并） void mergeSort(vector<int>& arr, int L, int R) { if (L >= R) return; // 子数组长度≤1，直接返回 int M = L + (R - L) / 2; // 中间索引 mergeSort(arr, L, M); // 左半部分排序,通过递归持续拆分至生成一个只含两个元素的数组，此数组左右两侧必然分别有序 mergeSort(arr, M + 1, R); // 右半部分排序 merge(arr, L, M, R); // 合并 }

快速排序

void quickSort(int arr[], int left, int right) { if (left >= right) return; // 递归终止条件：子数组长度≤1 // 1. 基准选择：中间位置元素（原 partition 逻辑嵌入） int mid = (left + right) / 2; swap(arr[left], arr[mid]); // 中间元素交换到 left 位置，统一处理 int pivot = arr[left]; // 基准值（原中间元素） int i = left, j = right; // 2. 双指针分区（原 partition 核心逻辑） while (i < j) { // 右指针向左找第一个小于基准的元素 while (i < j && arr[j] >= pivot) j--; // 左指针向右找第一个大于基准的元素 while (i < j && arr[i] <= pivot) i++; // 交换两元素 if (i < j) swap(arr[i], arr[j]); } // 3. 基准归位 swap(arr[left], arr[i]); int pivotPos = i; // 基准最终位置 // 4. 递归排序左右子数组 quickSort(arr, left, pivotPos - 1); quickSort(arr, pivotPos + 1, right); } // 测试代码（仅用于验证，核心仅 quickSort 函数） int main() { int arr[] = { 3, 6, 8, 5, 2, 9, 1, 7, 4 }; int n = sizeof(arr) / sizeof(arr[0]); cout << "排序前："; for (int i = 0; i < n; i++) cout << arr[i] << " "; quickSort(arr, 0, n - 1); // 仅调用 quickSort 函数 cout << "\n排序后："; for (int i = 0; i < n; i++) cout << arr[i] << " "; return 0; }

贪心算法

通过局部最优实现全局最优

pair对组

成对出现的数据，利用对组可以返回两个数据

创建

pair<string, int>p1("Tom",20); cout << p1.first << p1.second; pair<string, int>p2("Make", 30); cout << p2.first << p2.second;

双指针（尺取法）

核心思路：将二维循环改为一维循环

类型
​
- ①反向扫描：i、j 方向相反，i 从头到尾，j 从尾到头，在中间相会（左右指针）
​
- ②同向扫描：i、j 方向相同，都从头到尾，速度不同（如 j 跑在前，快慢指针）

二进制

1>~ :取反，0->1 1->0

2>正数最高位为0，负数最高位为1.

3>正数转负数：先-1，后~

4>负数转正数：先~,后+1

位运算

位运算的核心概念

位运算的操作对象是二进制位（bit）（0 或 1），支持对整数进行位运算，不支持浮点数。

• 一个字节（byte）= 8 位（bit），比如整数5的二进制（以 8 位为例）是00000101。
• 位运算的结果也是整数，所有操作都基于二进制逐位计算。

• 注意其二进制位，例如 int 型 不能左移33位，即1>>32不对 应为1L>>33

6 种核心位运算符

>>>不论正负一律以0补位

关键补充说明：1

1. 按位与（&）—— 最常用场景

   • 判断奇偶（核心用法）：num & 1
     • 偶数的二进制最后一位是 0 →num & 1 = 0（如4 & 1 = 0）；
     • 奇数的二进制最后一位是 1 →num & 1 = 1（如5 & 1 = 1）。
   • 提取指定位：比如取num的第 3 位 →num & (1 << 2)（1 左移 2 位是00000100，只有第 3 位为 1）。

2. 按位或（|）—— 置 1 操作

   • 把指定位设为 1：比如把num的第 2 位设为 1 →num | (1 << 1)（无论原位是 0/1，结果都为 1）。

3. 按位异或（^）—— 交换 / 翻转位

   • 不临时变量交换两个数：a = a ^ b; b = a ^ b; a = a ^ b;（仅适用于整数）；
   • 翻转指定位：比如翻转num的第 4 位 →num ^ (1 << 3)（0 变 1，1 变 0）。

4. 左移 / 右移（<</>>）—— 快速乘除 2

   • 左移 n 位 = 乘以2n：num << 1→ 乘 2，num << 2→ 乘 4（效率远高于*）；
   • 右移 n 位 = 除以2n（向下取整）：num >> 1→ 除以 2，9 >> 1 = 4（而非 4.5）。

位运算的实用场景（新手必懂）

1. 性能优化（替代算术运算）

• 奇偶判断：num & 1替代num % 2（位运算直接操作二进制，比取模快）；
• 乘除 2

二叉树

遍历

递归实现

非递归实现

处理输入输出

递归与master公式

符合master公式则可被计算时间复杂度

归并排序

稳定排序

n*logn

//合并两个有序区间 void mer(vector<int>& nums, int l, int r) { vector<int>help; help.reserve(r - l + 1); int m = (l + r) / 2; int i = l, j = m + 1; while (i <= m && j <= r) { if (nums[i] >= nums[j])help.push_back(nums[j++]); else help.push_back(nums[i++]); } while (i <= m) help.push_back(nums[i++]); while (j <= r)help.push_back(nums[j]); for (int p = 0; p < help.size(); p++) nums[l + p] = help[p]; } // 递归 void sort(vector<int>& nums, int l, int r) { if (l >= r)return; int m = l + (r - l) / 2; sort(nums, l, m); sort(nums, m + 1, r); mer(nums, l, r); } //非递归 //先合并相邻的 1 个元素、再合并相邻的 2 个元素、4 个元素…… 直到覆盖整个数组 vector<int> sortArray(vector<int>& nums) { int n = nums.size(); // 步长从 1 开始，每次翻倍（1→2→4→8...） for (int step = 1; step < n; step *= 2) { // 按当前步长合并相邻区间 for (int left = 0; left < n; left += 2 * step) { int mid = left + step - 1; // 处理最后一个区间可能不足 step 的情况 if (mid >= n - 1) break; // right 取 "left+2*step-1" 和 "n-1" 中的较小值，避免越界 int right = min(left + 2 * step - 1, n - 1); merge(nums, left, mid, right); } } return nums; }

随机快速排序

// 分区函数：返回基准元素最终位置 int partition(vector<int>& nums, int left, int right) { // 随机选基准并交换到区间末尾 int rand_idx = left + rand() % (right - left + 1); swap(nums[rand_idx], nums[right]); int pivot = nums[right]; int i = left - 1; // 小于等于基准的区域边界 for (int j = left; j < right; ++j) { if (nums[j] <= pivot) { swap(nums[++i], nums[j]); } } swap(nums[i + 1], nums[right]); // 基准归位 return i + 1; } // 快速排序递归核心函数 void quickSort(vector<int>& nums, int left, int right) { if (left >= right) return; int p = partition(nums, left, right); quickSort(nums, left, p - 1); quickSort(nums, p + 1, right); } // 对外暴露的排序入口函数 vector<int> sortArray(vector<int>& nums) { if (nums.empty()) return nums; srand(time(nullptr)); // 初始化随机数种子 quickSort(nums, 0, nums.size() - 1); return nums; }

荷兰国旗优化

#include <vector> #include <cstdlib> #include <ctime> using namespace std; // 荷兰国旗分区：返回等于基准区域的[左边界, 右边界] void partition(vector<int>& nums, int left, int right, int& lt, int& gt) { // 1. 随机选择基准并交换到区间开头 int rand_idx = left + rand() % (right - left + 1); swap(nums[rand_idx], nums[left]); int pivot = nums[left]; // 2. 初始化三区边界 lt = left; // 小于区右边界（初始为基准位置） gt = right; // 大于区左边界 int i = left + 1; // 遍历指针 // 3. 遍历划分三区 while (i <= gt) { if (nums[i] < pivot) { // 当前元素 < 基准：交换到小于区，扩大小于区，遍历指针右移 swap(nums[i++], nums[lt++]); } else if (nums[i] > pivot) { // 当前元素 > 基准：交换到大于区，扩大大于区（遍历指针不移动，需重新检查新交换来的元素） swap(nums[i], nums[gt--]); } else { // 当前元素 == 基准：直接右移遍历指针 i++; } } } // 快速排序递归函数（荷兰国旗优化） void quickSort(vector<int>& nums, int left, int right) { if (left >= right) return; int lt, gt; // 接收等于基准区域的左右边界 partition(nums, left, right, lt, gt); quickSort(nums, left, lt - 1); // 递归处理小于区 quickSort(nums, gt + 1, right); // 递归处理大于区 } // 排序入口函数 vector<int> sortArray(vector<int>& nums) { if (nums.empty()) return nums; srand(time(nullptr)); // 初始化随机数种子 quickSort(nums, 0, nums.size() - 1); return nums; }

随机选择

类似只递归一边的快速排序

// 荷兰国旗分区：返回等于基准区域的[左边界, 右边界] void partition(vector<int>& nums, int left, int right, int& lt, int& gt) { // 1. 随机选择基准（核心优化：避免有序数组的最坏情况） int rand_idx = left + rand() % (right - left + 1); swap(nums[rand_idx], nums[left]); int pivot = nums[left]; // 2. 划分小于/等于/大于三区 lt = left; gt = right; int i = left + 1; while (i <= gt) { if (nums[i] < pivot) { swap(nums[i++], nums[lt++]); } else if (nums[i] > pivot) { swap(nums[i], nums[gt--]); } else { i++; } } } // 随机选择核心函数：找 [left, right] 区间内第 k 小元素（k 从 0 开始计数） int randomSelect(vector<int>& nums, int left, int right, int k) { if (left == right) return nums[left]; // 区间只有一个元素，直接返回 int lt, gt; partition(nums, left, right, lt, gt); // 分区得到等于区边界 // 3. 判断 k 落在哪个区间，定向递归 if (k < lt) { // k 在小于区：递归处理 [left, lt-1] return randomSelect(nums, left, lt - 1, k); } else if (k > gt) { // k 在大于区：递归处理 [gt+1, right] return randomSelect(nums, gt + 1, right, k); } else { // k 在等于区：直接返回基准值（等于区所有元素都是第 k 小） return nums[lt]; } } // 入口函数：找数组中第 k 小元素（k 从 0 开始，如 k=0 是最小元素） int findKthSmallest(vector<int>& nums, int k) { if (nums.empty() || k < 0 || k >= nums.size()) { return -1; // 非法输入处理 } srand(time(nullptr)); // 初始化随机数种子 return randomSelect(nums, 0, nums.size() - 1, k); }

堆

堆结构

大/小根堆的构建算法

heapInsert (向上调整）

heapify（向下调整）

堆排序

堆排序优化：从底到顶建堆