历年算法题题源及题解¶
2009¶
Info
已知一个带有表头结点的单链表，结点结构为
，假设该链表只给出了头指针 list 。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第 𝑘 个位置上的结点（ 𝑘 为正整数）。若查找成功，算法输出该结点的 data 域的值，并返回 1 ；否则，只返回 0 。要求：
⑴ 描述算法的基本设计思想。
⑵ 描述算法的详细实现步骤。
⑶ 根据设计思想和实现步骤，采用程序设计语言描述算法（使用C或C++实现），关键之处请给出简要注释。
本题考察链表指针的使用。
题源:力扣 19. 删除链表的倒数第 N 个结点 真题为带有表头结点的单链表且要删除结点，该题为不带表头结点的单链表。
题解：
注意题目中单链表带表头结点，表头结点的 data 域不包含关键字。
方法一：单指针
求出链表的长度 𝑛 （不包含表头结点），然后顺序遍历到链表的第 𝑛−𝑘+1 个结点返回即可。从第 1 个结点出发，移动 𝑛−𝑘 步可到达第 𝑛−𝑘+1 个结点。
C代码如下：
// 获取链表倒数第k个元素
int getKthFromEnd(struct ListNode* list, int k) {
struct ListNode *node = list->link; // 跳过头节点
int n = 0; // 记录链表节点个数
while (node != NULL) { // 遍历链表
n++;
node = node->link;
}
node = list->link; // 重新指向第一个有效节点
int step = n - k; // 计算从第一个有效节点到倒数第k个节点的步数
if (step < 0) { // 如果k大于链表长度
return 0;
}
while (step) { // 移动到倒数第k个节点
node = node->link;
step--;
}
printf("%d", node->data); // 打印倒数第k个节点的数据
return 1;
}
#include <stdio.h>
#include <stdlib.h>
// 定义链表中元素的类型
typedef int ElemType;
// 定义链表节点结构体
struct ListNode {
ElemType data; // 数据部分
struct ListNode *link; // 指向下一个节点的指针
};
// 获取链表倒数第k个元素
int getKthFromEnd(struct ListNode* list, int k) {
struct ListNode *node = list->link; // 跳过头节点
int n = 0; // 记录链表节点个数
while (node != NULL) { // 遍历链表
n++;
node = node->link;
}
node = list->link; // 重新指向第一个有效节点
int step = n - k; // 计算从第一个有效节点到倒数第k个节点的步数
if (step < 0) { // 如果k大于链表长度
return 0;
}
while (step) { // 移动到倒数第k个节点
node = node->link;
step--;
}
printf("%d", node->data); // 打印倒数第k个节点的数据
return 1;
}
// 创建链表
struct ListNode* createLinkedList(ElemType *a, int n) {
struct ListNode* head = (struct ListNode *)malloc(sizeof(struct ListNode));
struct ListNode* tail = head;
for (int i = 0; i < n; i++) {
struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
node->data = a[i];
node->link = NULL;
tail->link = node;
tail = tail->link;
}
return head;
}
// 主函数
int main() {
ElemType a[] = {1, 2, 3, 4, 5};
struct ListNode* head = createLinkedList(a, 5);
getKthFromEnd(head, 2); // 期望输出: 4
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
// 定义链表中元素的类型
typedef int ElemType;
// 定义链表节点结构体
struct ListNode {
ElemType data; // 数据部分
ListNode *link; // 指向下一个节点的指针
};
// 获取链表倒数第k个元素
int getKthFromEnd(ListNode* list, int k) {
ListNode *node = list->link; // 跳过头节点
int n = 0; // 记录链表节点个数
while (node != nullptr) { // 遍历链表
n++;
node = node->link;
}
node = list->link; // 重新指向第一个有效节点
int step = n - k; // 计算从第一个有效节点到倒数第k个节点的步数
if (step < 0) { // 如果k大于链表长度
return 0;
}
while (step) { // 移动到倒数第k个节点
node = node->link;
step--;
}
cout << node->data; // 输出倒数第k个节点的数据
return 1;
}
// 创建链表
ListNode* createLinkedList(vector<ElemType> nums) {
ListNode* head = new ListNode();
ListNode* tail = head;
for (int i = 0; i < nums.size(); i++) {
ListNode* node = new ListNode();
node->data = nums[i];
node->link = nullptr;
tail->link = node;
tail = tail->link;
}
return head;
}
// 主函数
int main() {
vector<ElemType> a = {1, 2, 3, 4, 5};
ListNode* head = createLinkedList(a);
getKthFromEnd(head, 2); // 期望输出: 4
return 0;
}
复杂度分析
- 时间复杂度： 𝑂(𝑛) 。其中 𝑛 为链表的长度。需要遍历两次链表。
- 空间复杂度： 𝑂(1) 。使用了常数个辅助变量。
方法二：双指针
前后指针的思想。我们将第一个指针 fast 指向链表的第 𝑘+1 个元素所在结点，第二个指针 slow 指向链表的第 1 个元素所在结点，此时指针 fast 与slow 之间刚好间隔 𝑘 个结点。此时两个指针同步向后走，当第一个指针 fast 走到链表的尾部空结点时，则此时slow 指针刚好指向链表的倒数第 𝑘 个结点。
// 获取链表倒数第k个元素
int getKthFromEnd(struct ListNode* list, int k) {
struct ListNode *fast = list->link, *slow = list->link;
// 让fast指针先走k步
for (int i = 0; i < k; ++i) {
if (fast == NULL) return 0; // 如果链表长度小于k，返回0
fast = fast->link;
}
// 同时移动fast和slow指针，直到fast指向链表末尾
while (fast != NULL) {
fast = fast->link;
slow = slow->link;
}
// slow指向的节点即为倒数第k个节点
printf("%d", slow->data);
return 1;
}
#include <stdio.h>
#include <stdlib.h>
// 定义链表中元素的类型
typedef int ElemType;
// 定义链表节点结构体
struct ListNode {
ElemType data; // 数据部分
struct ListNode *link; // 指向下一个节点的指针
};
// 获取链表倒数第k个元素
int getKthFromEnd(struct ListNode* list, int k) {
struct ListNode *fast = list->link, *slow = list->link;
// 让fast指针先走k步
for (int i = 0; i < k; ++i) {
if (fast == NULL) return 0; // 如果链表长度小于k，返回0
fast = fast->link;
}
// 同时移动fast和slow指针，直到fast指向链表末尾
while (fast != NULL) {
fast = fast->link;
slow = slow->link;
}
// slow指向的节点即为倒数第k个节点
printf("%d", slow->data);
return 1;
}
// 创建链表
struct ListNode* createLinkedList(ElemType *a, int n) {
struct ListNode* head = (struct ListNode *)malloc(sizeof(struct ListNode));
struct ListNode* tail = head;
for (int i = 0; i < n; i++) {
struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
node->data = a[i];
node->link = NULL;
tail->link = node;
tail = tail->link;
}
return head;
}
// 主函数
int main() {
ElemType a[] = {1, 2, 3, 4, 5};
struct ListNode* head = createLinkedList(a, 5);
getKthFromEnd(head, 2); // 期望输出: 4
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
// 定义链表中元素的类型
typedef int ElemType;
// 定义链表节点结构体
struct ListNode {
ElemType data; // 数据部分
ListNode *link; // 指向下一个节点的指针
};
// 获取链表倒数第k个元素
int getKthFromEnd(ListNode* list, int k) {
ListNode *fast = list->link, *slow = list->link; // 初始化快慢指针
// 让fast指针先走k步
for (int i = 0; i < k; ++i) {
if (fast == nullptr) return 0; // 如果链表长度小于k，返回0
fast = fast->link;
}
// 同时移动fast和slow指针，直到fast指向链表末尾
while (fast) {
fast = fast->link;
slow = slow->link;
}
// slow指向的节点即为倒数第k个节点
cout << slow->data;
return 1;
}
// 创建链表
ListNode* createLinkedList(const vector<ElemType>& nums) {
ListNode* head = new ListNode();
ListNode* tail = head;
// 遍历数组并创建链表节点
for (int i = 0; i < nums.size(); i++) {
ListNode* node = new ListNode();
node->data = nums[i];
node->link = nullptr;
tail->link = node;
tail = tail->link;
}
return head;
}
// 主函数
int main() {
vector<ElemType> a = {1, 2, 3, 4, 5}; // 初始化测试数据
ListNode* head = createLinkedList(a); // 创建链表
getKthFromEnd(head, 2); // 期望输出: 4
return 0;
}
复杂度分析
- 时间复杂度： 𝑂(𝑛) 。其中 𝑛 为链表的长度。需要遍历一次链表。
- 空间复杂度： 𝑂(1) 。使用了常数个辅助变量。
2010¶
Info
42题： 设将 𝑛(𝑛>1) 个整数存放到一维数组 𝑅 中。试设计一个在时间和空间两方面都尽可能高效的算法。将 𝑅 中保存的序列循环左移 𝑝(0<𝑝<𝑛) 个位置，即将 𝑅 中的数据由 ⟨𝑋0,𝑋1,…,𝑋𝑛−1⟩ 变换为 ⟨𝑋𝑝,𝑋𝑝+1,…,𝑋𝑛−1,𝑋0,𝑋1,…,𝑋𝑝−1⟩ 。要求：
⑴ 给出算法的基本设计思想。
⑵ 根据设计思想，采用C或C++或Java语言描述，关键之处给出注释。
⑶ 说明你所设计算法的时间复杂度和空间复杂度。
题源： 本题考察数组元素的移动，即数组指针的使用。
力扣 189. 轮转数组 相似度：80%，真题为左旋，该题为右旋。
LCR 182. 动态口令 相似度：90%，真题为数组，该题为字符串。 题目难度：⭐️⭐️
题解：
方法一：使用辅助数组
我们可以利用数组随机访问的性质，使用辅助数组来将每个元素放至正确的位置。遍历原数组，将原数组下标为 𝑖 的元素放至新数组下标为 (𝑖−𝑝)mod 𝑛 的位置，最后将新数组拷贝至原数组即可。
但要注意，C或C++或Java语言中，负数取模的结果小于等于0，例如 (-1) % 3 返回 -1 而不是 2，当 𝑖−𝑝<0 时以对 𝑖−𝑝 模 𝑛 的结果为下标访问数组可能导致数组越界，所以在取模运算前加上一个数组长度 𝑛 。
#include <stdio.h>
void rotate(int* a, int n, int p) {
int newArr[n];
for (int i = 0; i < n; i++) {
newArr[(i - p + n) % n] = a[i];
}
for (int i = 0; i < n; i++) {
a[i] = newArr[i];
}
}
int main() {
int a[] = {1, 2, 3, 4, 5};
rotate(a, 5, 2);
for (int i = 0; i < 5; i++) {
printf("%d", a[i]);
}
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
void rotate(vector<int>& a, int p) {
int n = (int)a.size();
vector<int> newArr(n);
for (int i = 0; i < n; ++i) {
newArr[(i - p + n) % n] = a[i];
}
for (int i = 0; i < n; ++i) {
a[i] = newArr[i];
}
}
int main() {
vector<int> a = {1, 2, 3, 4, 5};
rotate(a, 2);
for (int i = 0; i < 5; i++) {
cout << a[i];
}
return 0;
}
复杂度分析
- 时间复杂度： 𝑂(𝑛) 。总共遍历两遍数组。
- 空间复杂度： 𝑂(𝑛) 。开辟大小为 𝑛 的辅助数组。
方法二：环状替换
我们从位置0开始，最初令 𝑡𝑒𝑚𝑝=𝐴[0] 。根据规则，位置 0 的元素会放至 (0−𝑝)mod𝑛 的位置，令 𝑥=(0−𝑝)mod𝑛 ，此时交换 𝑡𝑒𝑚𝑝 和 𝐴[𝑥] ，完成位置 𝑥 的更新。然后，我们考察位置 𝑥 ，并交换 𝑡𝑒𝑚𝑝 和 𝐴[(𝑥−𝑝)mod𝑛] ，从而完成下一个位置的更新。不断进行上述过程，直至回到初始位置 0 。
由于最终回到了起点，故该过程恰好走了整数数量的圈，不妨设为 𝑎 圈；再设该过程总共遍历了 𝑏 个元素。因此，我们有 𝑎𝑛=𝑏𝑝 ，即 𝑎𝑛 一定为 𝑛 和 𝑝 的公倍数。又因为我们在第一次回到起点时就结束，因此 𝑎 要尽可能小，故 𝑎𝑛 一定为 𝑛 和 𝑝 的最小公倍数 lcm(𝑛,𝑝) ，其中 lcm 表示最小公倍数。 𝑏=lcm(𝑛,𝑝)/𝑝 。
每轮遍历访问 𝑏=lcm(𝑛,𝑝)/𝑝 个元素，需要 𝑛/𝑏=gcd(𝑛,𝑝) 轮才能遍历所有元素，其中 gcd 表示最大公约数。
#include <stdio.h>
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
void rotate(int* a, int n, int p) {
int count = gcd(p, n);
for (int start = 0; start < count; ++start) {
int current = start;
int prev = a[start];
do {
int next = (current - p + n) % n;
swap(&a[next], &prev);
current = next;
} while (start != current);
}
}
int main() {
int a[] = {1, 2, 3, 4, 5};
rotate(a, 5, 2);
for (int i = 0; i < 5; i++) {
printf("%d", a[i]);
}
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
void rotate(vector<int>& a, int p) {
int n = (int)a.size();
int count = gcd(p, n);
for (int start = 0; start < count; ++start) {
int current = start;
int prev = a[start];
do {
int next = (current - p + n) % n;
swap(a[next], prev);
current = next;
} while (start != current);
}
}
int main() {
vector<int> a = {1, 2, 3, 4, 5};
rotate(a, 2);
for (int i = 0; i < 5; i++) {
cout << a[i];
}
return 0;
}
复杂度分析
- 时间复杂度： 𝑂(𝑛) 。数组中每个元素被遍历一次。
- 空间复杂度： 𝑂(1) 。使用常数个辅助变量。
方法三：数组翻转
我们可以先将所有元素翻转，这样尾部的 𝑛−𝑝 个元素就被移至数组头部，然后我们再翻转 𝐴[0:𝑛−𝑝−1] 和 𝐴[𝑛−𝑝:𝑛−1] 即能得到最后的答案。
#include <stdio.h>
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
void reverse(int* a, int start, int end) {
while (start < end) {
swap(&a[start], &a[end]);
start += 1;
end -= 1;
}
}
void rotate(int* a, int n, int p) {
reverse(a, 0, n - 1);
reverse(a, 0, n - p - 1);
reverse(a, n - p, n - 1);
}
int main() {
int a[] = {1, 2, 3, 4, 5};
rotate(a, 5, 2);
for (int i = 0; i < 5; i++) {
printf("%d", a[i]);
}
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
void reverse(vector<int>& a, int start, int end) {
while (start < end) {
swap(a[start], a[end]);
start += 1;
end -= 1;
}
}
void rotate(vector<int>& a, int p) {
int n = (int)a.size();
reverse(a, 0, n - 1);
reverse(a, 0, n - p - 1);
reverse(a, n - p, n - 1);
}
int main() {
vector<int> a = {1, 2, 3, 4, 5};
rotate(a, 2);
for (int i = 0; i < 5; i++) {
cout << a[i];
}
return 0;
}
复杂度分析
- 时间复杂度： 𝑂(𝑛) 。数组中每个元素被交换两次。
- 空间复杂度： 𝑂(1) 。使用常数个辅助变量。
2011¶
Info
42题：一个长度为 𝐿(𝐿≥1) 的升序序列 𝑆 ，处在第 ⌈𝐿/2⌉ 个位置的数称为 𝑆 的中位数。例如，若序列 𝑆1=⟨11,13,15,17,19⟩ ，则 𝑆1 的中位数是 15 。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若序列 𝑆2=⟨2,4,6,8,20⟩ ，则 𝑆1 和 𝑆2 的中位数是 11 。现有两个等长的升序序列 𝐴 和 𝐵 ，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列 𝐴 和 𝐵 的中位数。要求：
⑴ 给出算法的基本设计思想。
⑵ 根据设计思想，采用C或C++或Java语言描述，关键之处给出注释。
⑶ 说明你所设计算法的时间复杂度和空间复杂度。
题源分析：本题深入考察了二分查找及二分查找的变体，本质考察分治法。
力扣 4. 寻找两个正序数组的中位数 相似度：70%，真题为两个等长的升序序列且返回下中位数，本题为两个大小分别为 m 和 n 的升序数组且返回上中位数和下中位数的平均数。
PAT甲级 1029 Median 相似度：75%，真题为两个等长的升序序列，本题为两个大小分别为 m 和 n 的升序数组。
《算法导论》第三版 9.3-8 或《算法导论》第四版 9.3-10。也是本题的实际来源。
相似度：90%，真题为C语言数组，数组下标从 0 开始，数组中可能存在相等元素，本题为伪代码，数组下标从 1 开始，数组中不存在相等元素。
题源判定：算法导论
AcWing 3819. 求两升序序列的中位数（来源：2011年全国硕士研究生招生考试）提供了本题的 OJ
题目难度：⭐️⭐️⭐️⭐️⭐️
2012¶
Info
42题：假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如，loading和being 的存储映像如下图所示。
设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为
，请设计一个时间上尽可能高效的算法，找出由str1和str2所指向两个链表共同后缀的起始位置（如图中字符i所在的结点位置p）。要求：
⑴ 给出算法的基本设计思想。
⑵ 根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
⑶ 说明你所设计算法的时间复杂度。
题源：本题考察链表指针的使用。
力扣 160. 相交链表 相似度：90%，真题为带有表头结点的单链表，该题为不带表头结点的单链表。
题目难度：⭐️⭐️
解：本题为简单难度的链表题，解决方法有很多，思维有一定难度。
注意，每个链表都具有头结点，设其中str1和str2的长度分别为 𝑛1 和 𝑛2。
方法一：双指针（差值法）
使用双指针的方法，可以将空间复杂度降至 𝑂(1) 。
创建两个指针 𝑝1和 𝑝2 ，初始时分别指向str1和str2的头结点，分别遍历两条链表，得到链表长度分别为 𝑙1 和 𝑙2 （不考虑头结点），计算两条链表长度差值 |𝑙1−𝑙2| ，然后将指针 𝑝1和 𝑝2 重新分别指向str1和str2的头结点，长的链表的指针先的走过差值长度|𝑙1−𝑙2| ，然后两个指针 𝑝1和 𝑝2 同步遍历两条链表，当指针 𝑝1 和 𝑝2 指向同一个结点或者都为空时，返回它们指向的结点或者NULL。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct ListNode {
int data;
struct ListNode *next;
};
struct ListNode *getIntersectionNode(struct ListNode *str1, struct ListNode *str2) {
int l1 = 0;
int l2 = 0;
struct ListNode *p1 = str1->next, *p2 = str2->next;
while (p1 != NULL) {
l1++;
p1 = p1->next;
}
while (p2 != NULL) {
l2++;
p2 = p2->next;
}
p1 = str1->next;
p2 = str2->next;
if (l1 > l2) {
int d = l1 - l2;
while (d > 0) {
p1 = p1->next;
d--;
}
} else if (l1 < l2) {
int d = l2 - l1;
while (d > 0) {
p2 = p2->next;
d--;
}
}
while (p1 != p2) {
p1 = p1->next;
p2 = p2->next;
}
return p1;
}
struct ListNode** createTwoLinkedList(char *s1, char *s2) {
int len1 = strlen(s1);
int len2 = strlen(s2);
int suffix_len = 0;
for (int i = len1 - 1, j = len2 - 1; i >= 0, j >= 0; i--, j--) {
if (s1[i] == s2[j]) {
suffix_len++;
} else {
break;
}
}
struct ListNode* head1 = (struct ListNode *)malloc(sizeof(struct ListNode));
struct ListNode* tail1 = head1;
struct ListNode* intersection_node = NULL;
int p1 = 0;
while (p1 < len1) {
struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
node->data = s1[p1];
node->next = NULL;
tail1->next = node;
tail1 = tail1->next;
if (p1 == len1 - suffix_len) {
intersection_node = node;
}
p1++;
}
struct ListNode* head2 = (struct ListNode *)malloc(sizeof(struct ListNode));
struct ListNode* tail2 = head2;
int p2 = 0;
while (p2 < len2) {
struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
node->data = s2[p2];
node->next = NULL;
tail2->next = node;
tail2 = tail2->next;
p2++;
if (p2 == len2 - suffix_len) {
node->next = intersection_node;
break;
}
}
struct ListNode* hs[] = {head1, head2};
return hs;
}
int main() {
char *s1 = "loading";
char *s2 = "being";
struct ListNode** strs = createTwoLinkedList(s1, s2);
struct ListNode* str1 = strs[0];
struct ListNode* str2 = strs[1];
struct ListNode* intersectionNode = getIntersectionNode(str1, str2);
if (intersectionNode != NULL) {
printf("%c", intersectionNode->data);
}
return 0;
}
#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct ListNode {
int data;
ListNode *next;
};
ListNode* getIntersectionNode(ListNode* str1, ListNode* str2) {
int l1 = 0;
int l2 = 0;
ListNode *p1 = str1->next, *p2 = str2->next;
while (p1 != nullptr) {
l1++;
p1 = p1->next;
}
while (p2 != nullptr) {
l2++;
p2 = p2->next;
}
p1 = str1->next;
p2 = str2->next;
if (l1 > l2) {
int d = l1 - l2;
while (d > 0) {
p1 = p1->next;
d--;
}
} else if (l1 < l2) {
int d = l2 - l1;
while (d > 0) {
p2 = p2->next;
d--;
}
}
while (p1 != p2) {
p1 = p1->next;
p2 = p2->next;
}
return p1;
}
vector<ListNode *> createTwoLinkedList(string s1, string s2) {
int len1 = s1.length();
int len2 = s2.length();
int suffix_len = 0;
for (int i = len1 - 1, j = len2 - 1; i >= 0, j >= 0; i--, j--) {
if (s1[i] == s2[j]) {
suffix_len++;
} else {
break;
}
}
ListNode* head1 = new ListNode();
ListNode* tail1 = head1;
ListNode* intersection_node = nullptr;
int p1 = 0;
while (p1 < len1) {
ListNode* node = new ListNode();
node->data = s1[p1];
node->next = nullptr;
tail1->next = node;
tail1 = tail1->next;
if (p1 == len1 - suffix_len) {
intersection_node = node;
}
p1++;
}
ListNode* head2 = new ListNode();
ListNode* tail2 = head2;
int p2 = 0;
while (p2 < len2) {
ListNode* node = new ListNode();
node->data = s2[p2];
node->next = nullptr;
tail2->next = node;
tail2 = tail2->next;
p2++;
if (p2 == len2 - suffix_len) {
node->next = intersection_node;
break;
}
}
return vector<ListNode *>{head1, head2};
}
int main() {
string s1 = "loading";
string s2 = "being";
vector<ListNode *> strs = createTwoLinkedList(s1, s2);
ListNode* str1 = strs[0];
ListNode* str2 = strs[1];
ListNode* intersectionNode = getIntersectionNode(str1, str2);
if (intersectionNode != nullptr) {
printf("%c", intersectionNode->data);
}
return 0;
}
复杂度分析
- 时间复杂度： 𝑂(𝑛1+𝑛2) 。需要遍历两个链表各一次。
- 空间复杂度： 𝑂(1) 。需要常数个辅助变量。
方法二：双指针
2013¶
Info
41题：已知一个整数序列 𝐴=(𝑎0,𝑎1,…,𝑎𝑛−1) ，其中 0≤𝑎𝑖<𝑛(0≤𝑖<𝑛) 。若存在 𝑎𝑝1=𝑎𝑝2=⋯=𝑎𝑝𝑚=𝑥 且 𝑚>𝑛/2(0≤𝑝𝑘<𝑛,1≤𝑘≤𝑚) ，则称 𝑥 为 𝐴 的主元素。例如 𝐴=(0,5,5,3,5,7,5,5) ，则 5 为主元素；又如 𝐴=(0,5,5,3,5,1,5,7) ，则 𝐴 中没有主元素。假设 𝐴 中的 𝑛 个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出 𝐴 的主元素。若存在主元素，则输出该元素；否则输出 −1 。要求：
⑴ 给出算法的基本设计思想。
⑵ 根据设计思想，采用C、C++或Java语言描述算法，关键之处给出注释。
⑶ 说明你所设计算法的时间复杂度和空间复杂度。
本题考察计数法或者摩尔投票法。
力扣 169. 多数元素 相似度：90%，真题不一定存在主元素，该题为一定存在主元素。
程序员面试金典 面试题 17.10. 主要元素 相似度：100%。
题源判定：程序员面试金典
题目难度：⭐️⭐️⭐️⭐
️方法一：散列表
由于 0≤𝑎𝑖<𝑛 ，我们只需要构造辅助数组 𝐶[0:𝑛] 作为散列表进行计数。
我们设定出现次数最多的为候选元素。
题目告诉我们主元素不一定存在，所以最后我们要检查的候选元素在序列中的出现次数，如果大于 𝑛/2 才能最终确定为主元素。
C代码如下（含测试用例）：
#include <stdio.h>
#include <string.h>
int majorityElement(int *a, int n) {
int cnts[n + 1];
memset(cnts, 0, sizeof(cnts));
int majority = 0, max_cnt = 0;
for (int i = 0; i < n; ++i) {
cnts[a[i]]++;
if (cnts[a[i]] > max_cnt) {
majority = a[i];
max_cnt = cnts[a[i]];
}
}
return max_cnt > n / 2 ? majority : -1;
}
int main() {
int a[] = {0,5,5,3,5,7,5,5};
int x = majorityElement(a, 8);
if (x != -1) {
printf("%d", x);
}
return 0;
}
C++代码如下（含测试用例）：
#include <iostream>
#include <vector>
using namespace std;
int majorityElement(vector<int>& nums) {
const int n = (int)nums.size();
vector<int>counts(n + 1);
int majority = 0, max_count = 0;
for (int i = 0; i < n; ++i) {
++counts[nums[i]];
if (counts[nums[i]] > max_count) {
majority = nums[i];
max_count = counts[nums[i]];
}
}
return max_count > n / 2 ? majority : -1;
}
int main() {
vector<int> a = {0,5,5,3,5,7,5,5};
int x = majorityElement(a);
if (x != -1) {
cout << x;
}
return 0;
}
复杂度分析
- 时间复杂度： 𝑂(𝑛) 。我们遍历数组一次，对于数组中的每一个元素，计数和比较的时间为常数。
- 空间复杂度： 𝑂(𝑛) 。开辟了大小为 𝑂(𝑛) 的辅助数组。
注：考试中一般会给出关键字的值域，没必要使用unordered_set或unordered_map，而且使用数组作为散列表的运行效率比采用unordered_set或unordered_map作为散列表的运行效率高很多。
方法二：摩尔投票算法
如果我们把主元素记为 +1 ，把其他数记为 −1 ，将它们全部加起来，显然和大于 0 ，从结果本身我们可以看出主元素的个数比其他数的总数多。
这个描述比较抽象， +1 和 −1 相消为 0 ，本质就是一个同归于尽的思路，
我们设考察元素为候选元素，出现候选元素计数 +1 ，遇到非候选元素计数 −1 ，如果候选元素计数为负，此时切换候选元素为最新检查的元素。
题目告诉我们主元素不一定存在，所以最后我们要检查的候选元素在序列中的出现次数，如果大于 𝑛/2 才能最终确定为主元素。
C代码如下（含测试用例）：
#include <stdio.h>
int majorityElement(int *a, int n) {
int candidate = -1;
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (a[i] == candidate) {
++cnt;
} else if (--cnt < 0) {
candidate = a[i];
cnt = 1;
}
}
cnt = 0;
for (int i = 0; i < n; ++i) {
if (a[i] == candidate) {
++cnt;
}
}
return cnt > n / 2 ? candidate : -1;
}
int main() {
int a[] = {0,5,5,3,5,7,5,5};
int x = majorityElement(a, 8);
if (x != -1) {
printf("%d", x);
}
return 0;
}
C++代码如下（含测试用例）：
#include <iostream>
#include <vector>
using namespace std;
int majorityElement(vector<int>& nums) {
const int n = (int)nums.size();
int candidate = -1;
int count = 0;
for (int i = 0; i < n; ++i) {
if (nums[i] == candidate) {
++count;
} else if (--count < 0) {
candidate = nums[i];
count = 1;
}
}
count = 0;
for (int i = 0; i < n; ++i) {
if (nums[i] == candidate) {
++count;
}
}
return count > n / 2 ? candidate : -1;
}
int main() {
vector<int> a = {0,5,5,3,5,7,5,5};
int x = majorityElement(a);
if (x != -1) {
cout << x;
}
return 0;
}
复杂度分析
- 时间复杂度： 𝑂(𝑛) 。我们遍历数组两次，第一次遍历数组用摩尔投票算法找出最多的元素，第二次遍历数组统计该元素个数，最后检查该元素个数是否大于 𝑛/2 。
- 空间复杂度： 𝑂(1) 。只用了常数个辅助变量。
方法三：快速排序 + 中位数
若 𝐴 存在主元素，则该数组的中位数一定是主元素，包括 𝑛 为奇数时的中位数和 𝑛 为偶数时的下中位数和上中位数。
第一步：对 𝐴 进行排序，一般采用快速排序。
第二步：取出中位数，用二分查找统计中位数数量，最后检查中位数个数是否大于 𝑛/2 。
C代码如下：
#include <stdio.h>
#include <stdlib.h>
void swap(int *a, int i, int j){
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
int partition(int *a, int p, int r) {
int x = a[r];
int i = p - 1;
for (int j = p; j < r; ++j) {
if (a[j] <= x) {
++i;
swap(a, i, j);
}
}
swap(a, i + 1, r);
return i + 1;
}
int randomized_partition(int *a, int p, int r) {
int i = rand() % (r - p + 1) + p; // 随机选一个作为主元
swap(a, r, i);
return partition(a, p, r);
}
void randomized_quicksort(int *a, int p, int r) {
if (p < r) {
int q = randomized_partition(a, p, r);
randomized_quicksort(a, p, q - 1);
randomized_quicksort(a, q + 1, r);
}
}
int binary_search_first(int *a, int n, int target){
int left = 0, right = n - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
if(a[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
if (left != n && a[left] == target) return left;
return -1;
}
int binary_search_last(int *a, int n, int target){
int left = 0, right = n - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
if(a[mid] <= target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
if (right != -1 && a[right] == target) return right;
return -1;
}
int majorityElement(int *a, int n) {
randomized_quicksort(a, 0, n - 1);
int median = a[n / 2];
int first_index = binary_search_first(a, n, median);
int last_index = binary_search_last(a, n, median);
int cnt = last_index - first_index + 1;
return cnt > n / 2 ? median : -1;
}
int main() {
int a[] = {0,5,5,3,5,7,5,5};
int x = majorityElement(a, 8);
if (x != -1) {
printf("%d", x);
}
return 0;
}
复杂度分析：
- 时间复杂度： 𝑂(𝑛log𝑛) 。
- 空间复杂度： 𝑂(log𝑛) ，平均情况下递归栈深度为 𝑂(log𝑛) 。
方法四：选择算法 + 中位数
可以用选择算法对方法三进行优化，优化后代码如下：
递归版
C代码如下（含测试用例）：
#include <stdio.h>
#include <stdlib.h>
void swap(int *a, int i, int j){
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
int partition(int *a, int p, int r) {
int x = a[r];
int i = p - 1;
for (int j = p; j < r; ++j) {
if (a[j] <= x) {
++i;
swap(a, i, j);
}
}
swap(a, i + 1, r);
return i + 1;
}
int randomized_partition(int *a, int p, int r) {
int i = rand() % (r - p + 1) + p; // 随机选一个作为主元
swap(a, r, i);
return partition(a, p, r);
}
void randomized_select(int *a, int p, int r, int i) {
if (p == r) {
return;
}
int q = randomized_partition(a, p, r);
int k = q - p + 1;
if (i == k) {
return;
} else if (i < k) {
randomized_select(a, p, q - 1, i);
} else {
randomized_select(a, q + 1, r, i - k);
}
}
int majorityElement(int *a, int n) {
randomized_select(a, 0, n - 1, n / 2);
int median = a[n / 2];
int cnt = 0;
for (int i = 0; i < n; i++) {
if (a[i] == median) {
cnt++;
}
}
return cnt > n / 2 ? median : -1;
}
int main() {
int a[] = {0,5,5,3,5,7,5,5};
int x = majorityElement(a, 8);
if (x != -1) {
printf("%d", x);
}
return 0;
}
复杂度分析：
- 时间复杂度： 𝑂(𝑛) 。
- 空间复杂度： 𝑂(log𝑛) ，平均情况下递归栈深度为 𝑂(log𝑛) 。
迭代版
C代码如下（含测试用例）：
#include <stdio.h>
#include <stdlib.h>
void swap(int *a, int i, int j){
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
int partition(int *a, int p, int r) {
int x = a[r];
int i = p - 1;
for (int j = p; j < r; ++j) {
if (a[j] <= x) {
++i;
swap(a, i, j);
}
}
swap(a, i + 1, r);
return i + 1;
}
int randomized_partition(int *a, int p, int r) {
int i = rand() % (r - p + 1) + p; // 随机选一个作为主元
swap(a, r, i);
return partition(a, p, r);
}
void randomized_select(int *a, int p, int r, int i) {
int q, k;
while (1) {
q = partition(a, p, r);
k = q - p + 1;
if (i == k) {
return;
} else if (i < k) {
r = q - 1;
} else {
p = q + 1;
i = i - k;
}
}
}
int majorityElement(int *a, int n) {
randomized_select(a, 0, n - 1, n / 2);
int median = a[n / 2];
int cnt = 0;
for (int i = 0; i < n; i++) {
if (a[i] == median) {
cnt++;
}
}
return cnt > n / 2 ? median : -1;
}
int main() {
int a[] = {0,5,5,3,5,7,5,5};
int x = majorityElement(a, 8);
if (x != -1) {
printf("%d", x);
}
return 0;
}
复杂度分析：
- 时间复杂度： 𝑂(𝑛) 。
- 空间复杂度： 𝑂(1) ，使用了常数个辅助变量。
注：参考力扣169. 多数元素、面试题 17.10. 主要元素。
评：摩尔投票算法的思维难度很高，很难在考场上靠灵光一现就想出来，更多是靠平时积累。当然，摩尔投票算法难度可以进一步提升，感兴趣的同学可以做一下力扣229. 多数元素 II。这道题需要用到多指针或者指针数组。
2014¶
Note
41题:二叉树的带权路径长度（WPL）是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T，采用二叉链表存储，结点结构为：
其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针，请设计求T的WPL的算法，要求：
⑴ 给出算法的基本设计思想；
⑵ 使用C或C++语言，给出二叉树结点的数据类型定义；
⑶ 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
题源判定：命题组原创
AcWing 3766. 二叉树的带权路径长度（来源：2014年全国硕士研究生招生考试）提供了本题的 OJ。
题目难度：⭐️⭐️⭐️
解答：
本题为一道简单难度的考察搜索的算法题，考研只需要掌握深度优先搜索和广度优先搜索即可。
这道题要注意的是题目要求“二叉树中所有叶结点的带权路径长度之和”，也就是只有“叶结点”才需要计算WPL。
构造测试用例如下图所示：
方法一：深度优先搜索
C代码如下（含测试用例）：
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int weight;
struct TreeNode *left;
struct TreeNode *right;
};
int dfs(struct TreeNode* root, int depth) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return root->weight * depth;
}
return dfs(root->left, depth + 1) + dfs(root->right, depth + 1);
}
int pathSum(struct TreeNode* root) {
return dfs(root, 0);
}
struct TreeNode *createBinaryTree(int *a, int n) {
if (a[0] == -1) {
return NULL;
}
int i = 0;
struct TreeNode *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
root->weight = a[i++];
root->left = NULL;
root->right = NULL;
struct TreeNode** que = (struct TreeNode**)malloc(sizeof(struct TreeNode*));
int front = 0, rear = 0;
struct TreeNode *curr = root;
que[rear++] = curr;
while (front < rear && i < n) {
curr = que[front++];
for (int j = 0; j < 2 && i < n; j++, i++) {
if (a[i] != -1) {
if (j == 0) {
curr->left = (struct TreeNode *)malloc(sizeof(struct TreeNode));
curr->left->weight = a[i];
curr->left->left = NULL;
curr->left->right = NULL;
que[rear++] = curr->left;
} else {
curr->right = (struct TreeNode *)malloc(sizeof(struct TreeNode));
curr->right->weight = a[i];
curr->right->left = NULL;
curr->right->right = NULL;
que[rear++] = curr->right;
}
}
}
}
return root;
}
int main() {
int W[] = {1, -1, 2, 3};
printf("%d", pathSum(createBinaryTree(W, 4)));
return 0;
}
C++代码如下（含测试用例）：
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct TreeNode {
int weight;
TreeNode *left;
TreeNode *right;
TreeNode() : weight(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : weight(x), left(nullptr), right(nullptr) {}
};
int dfs(TreeNode* root, int depth) {
if (root == nullptr) {
return 0;
}
if (root->left == nullptr && root->right == nullptr) {
return root->weight * depth;
}
return dfs(root->left, depth + 1) + dfs(root->right, depth + 1);
}
int pathSum(TreeNode* root) {
return dfs(root, 0);
}
TreeNode *createBinaryTree(vector<int> weights) {
if (weights[0] == -1) {
return nullptr;
}
const int n = weights.size();
int i = 0;
TreeNode *root = new TreeNode(weights[i++]);
queue<TreeNode *> Q;
Q.push(root);
while (!Q.empty() && i < n) {
TreeNode *node = Q.front();
Q.pop();
for (int j = 0; j < 2 && i < n; j++, i++) {
if (weights[i] != -1) {
if (j == 0) {
node->left = new TreeNode(weights[i]);
Q.push(node->left);
} else {
node->right = new TreeNode(weights[i]);
Q.push(node->right);
}
}
}
}
return root;
}
int main() {
vector<int> W = {1, -1, 2, 3};
cout << pathSum(createBinaryTree(W));
return 0;
}
复杂度分析
- 时间复杂度： 𝑂(𝑛) ，其中 𝑛 是二叉树的结点数。
- 空间复杂度： 𝑂(𝑛) ，为递归过程中栈的开销，平均情况下为 𝑂(log𝑛) ，最坏情况下树呈现链状，为 𝑂(𝑛) 。
聪明的同学发现这个深度优先搜索就是二叉树的前序遍历，那么为什么此方法不命名为前序遍历呢？因为“根左右”递归顺序可以，“根右左”递归顺序也同样可以，当然也可以采用其它规则，所以王道将方法一命名为前序遍历是不严谨的。
深度优先搜索在二叉树遍历中的应用典型的有前序遍历，中序遍历，后序遍历。
深度优先搜索在一般树遍历中的应用典型的有先根遍历，后根遍历。
那么这些方法应该如何应用呢？
自顶向下搜索：二叉树通常用前序遍历，一般树通常用先根遍历。
自底向上搜索：二叉树通常用后序遍历，一般树通常用后根遍历。
从左到右搜索：二叉树通常用中序遍历，最常见的应用场景就是二叉搜索树的遍历。
很显然，本题的递归深度depth是自顶向下计算的，适用自顶向下搜索，二叉树中对应“根左右”递归遍历或者根右左”递归遍历，当然也可以采用其它规则，“根左右”递归遍历即前序遍历。
方法二：广度优先搜索
C代码如下（含测试用例）：
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int weight;
struct TreeNode *left;
struct TreeNode *right;
};
int pathSum(struct TreeNode* root) {
if (root == NULL) {
return 0;
}
struct TreeNode *curr = root;
struct TreeNode** que = (struct TreeNode**)malloc(sizeof(struct TreeNode*));
int front = 0, rear = 0;
que[rear++] = curr;
int wpl = 0;
int depth = 0;
while (front < rear) {
int sz = rear - front;
while (sz > 0) {
curr = que[front++];
if (curr->left == NULL && curr->right == NULL) {
wpl += curr->weight * depth;
}
if (curr->left) {
que[rear++] = curr->left;
}
if (curr->right) {
que[rear++] = curr->right;
}
sz--;
}
depth++;
}
return wpl;
}
struct TreeNode *createBinaryTree(int *a, int n) {
if (a[0] == -1) {
return NULL;
}
int i = 0;
struct TreeNode *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
root->weight = a[i++];
root->left = NULL;
root->right = NULL;
struct TreeNode** que = (struct TreeNode**)malloc(sizeof(struct TreeNode*));
int front = 0, rear = 0;
struct TreeNode *curr = root;
que[rear++] = curr;
while (front < rear && i < n) {
curr = que[front++];
for (int j = 0; j < 2 && i < n; j++, i++) {
if (a[i] != -1) {
if (j == 0) {
curr->left = (struct TreeNode *)malloc(sizeof(struct TreeNode));
curr->left->weight = a[i];
curr->left->left = NULL;
curr->left->right = NULL;
que[rear++] = curr->left;
} else {
curr->right = (struct TreeNode *)malloc(sizeof(struct TreeNode));
curr->right->weight = a[i];
curr->right->left = NULL;
curr->right->right = NULL;
que[rear++] = curr->right;
}
}
}
}
return root;
}
int main() {
int W[] = {1, -1, 2, 3};
printf("%d", pathSum(createBinaryTree(W, 4)));
return 0;
}
个人非常不喜欢用C语言写栈和队列等数据结构，灵活使用C语言的指针其实难度极大，比如这段代码中需要使用到指针的指针，建议使用C++。
C++代码如下（含测试用例）：
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct TreeNode {
int weight;
TreeNode *left;
TreeNode *right;
TreeNode() : weight(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : weight(x), left(nullptr), right(nullptr) {}
};
int pathSum(TreeNode* root) {
if (root == nullptr) {
return 0;
}
queue<TreeNode *>Q;
TreeNode *curr = root;
Q.push(curr);
int wpl = 0;
int depth = 0;
while (!Q.empty()) {
int sz = (int)Q.size();
while (sz > 0) {
curr = Q.front();
Q.pop();
if (curr->left == nullptr && curr->right == nullptr) {
wpl += curr->weight * depth;
}
if (curr->left) {
Q.push(curr->left);
}
if (curr->right) {
Q.push(curr->right);
}
sz--;
}
depth++;
}
return wpl;
}
TreeNode *createBinaryTree(vector<int> weights) {
if (weights[0] == -1) {
return nullptr;
}
const int n = weights.size();
int i = 0;
TreeNode *root = new TreeNode(weights[i++]);
queue<TreeNode *> Q;
Q.push(root);
while (!Q.empty() && i < n) {
TreeNode *node = Q.front();
Q.pop();
for (int j = 0; j < 2 && i < n; j++, i++) {
if (weights[i] != -1) {
if (j == 0) {
node->left = new TreeNode(weights[i]);
Q.push(node->left);
} else {
node->right = new TreeNode(weights[i]);
Q.push(node->right);
}
}
}
}
return root;
}
int main() {
vector<int> W = {1, -1, 2, 3};
cout << pathSum(createBinaryTree(W));
return 0;
}
复杂度分析
- 时间复杂度： 𝑂(𝑛) ，其中 𝑛 是二叉树的结点数。
- 空间复杂度： 𝑂(𝑛) ，队列中的元素不超过 𝑛 个。
聪明的同学发现本题的广度优先搜索用的就是二叉树的层序遍历，但是为什么此方法不命名为层序遍历呢？很显然，每层的遍历顺序是从左到右或者从右到左都是可以的，当然也可以采用其它规则，所以王道将方法二命名为层序遍历是不严谨的。
广度优先搜索在二叉树遍历中的应用典型的就是层序遍历。
层序遍历通常有两种写法：
第一种是多指针，维护一个last指针和tail指针，last指针指向当前层遍历到的结点，tail指针指向当前层最后一个结点，当last指针和tail指针重合的时候，说明需要开始遍历下一层了，遍历深度depth加一。
第二种是计算当前层的结点个数，当前层结点遍历结束就可以开始遍历下一层了，遍历深度depth加一。
本人给出的参考答案用的是第二种层序遍历写法，和力扣官方题解的风格一致，而且第二种写法相对简洁。
王道给出的参考答案用的是第一种层序遍历写法，有兴趣的同学可以自己尝试下，这里就不摘录该代码了。
评：王道提供的参考答案中存在结构体成员变量命名错误的问题：
按照题目要求应更正为：
后面代码中都要进行对应的修改。
结构体成员变量命名应该与题目要求一致。
注：本题可参考AcWing3766. 二叉树的带权路径长度。
2015¶
Note
41题: 用单链表保存 𝑚 个整数，结点的结构为，且 |data|≤𝑛 （ 𝑛 为正整数）。现要求设计一个时间复杂度尽可能高效的算法，对于链表中 data 的绝对值相等的结点， 仅保留第一次出现的结点而删除其余绝对值相等的结点 。例如，若给定的单链表 head 如下：
则删除结点后的 head 为：
要求：
⑴ 给出算法的基本设计思想。
⑵ 使用C或C++语言，给出单链表结点的数据类型定义。
⑶ 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
⑷ 说明你所设计算法的时间复杂度和空间复杂度。
本题考察计数法。
程序员面试金典 面试题 02.01. 移除重复节点 相似度：90%，真题为带有表头结点的单链表，该题为不带表头结点的单链表。
力扣 203. 移除链表元素 相似度：70%，真题为带有表头结点的单链表且保留最开始出现的结点，该题为不带表头结点的单链表且不保留最开始出现的结点。
题源判定：程序员面试金典
AcWing 3756. 筛选链表（来源：2015年全国硕士研究生招生考试）提供了本题的 OJ。
题目难度：⭐️⭐️
这道题没什么难度，本质就是考察链表的删除，注意审题，处理的是“绝对值”相等的结点，“仅保留第一次出现的结点”而删除其余绝对值相等的结点。
还有注意结点的结构为 datalink ，不是我们习惯的 valnext ，结构体成员变量命名要与题目要求一致。
注意，该链表带头结点，头结点的 data 为空。
方法一：散列表
题目要求“时间复杂度尽可能高效”，所以可以考虑用散列表进行辅助。
算法基本思想如下：
从链表第一个元素开始遍历链表：
如果散列表中没有绝对值为当前元素绝对值的记录，保留该结点，并在散列表中记录当前元素绝对值，继续检查下一个结点。
如果散列表中已经有绝对值为当前元素绝对值的记录，删除该结点，继续检查下一个结点。
直到链表遍历结束。
C代码如下（含测试用例）：
C语言没有散列表这种数据结构，可以考虑用数组代替，由题目条件 |data|≤𝑛 ，只需要开辟一个大小为 𝑛+1 的辅助数组。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct ListNode {
int data;
struct ListNode* link;
};
struct ListNode* deleteDuplicates(struct ListNode* head, int n) {
int st[n + 1];
memset(st, 0, sizeof(st));
struct ListNode *prev = head;
struct ListNode *curr = head->link;
while (curr != NULL) {
if (st[abs(curr->data)] == 1) {
prev->link = curr->link;
struct ListNode *temp = curr;
curr = curr->link;
free(temp);
} else {
st[abs(curr->data)] = 1;
prev = prev->link;
curr = curr->link;
}
}
return head;
}
struct ListNode* createLinkedList(int *a, int n) {
struct ListNode* head = (struct ListNode *)malloc(sizeof(struct ListNode));
struct ListNode* tail = head;
for (int i = 0; i < n; i++) {
struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
node->data = a[i];
node->link = NULL;
tail->link = node;
tail = tail->link;
}
return head;
}
int main(int argc, const char * argv[]) {
int a[] = {21, -15, -15, -7, 15};
struct ListNode* head = createLinkedList(a, 5);
struct ListNode* newhead = deleteDuplicates(head, 32);
struct ListNode* curr = head->link;
printf("head");
while (curr != NULL) {
printf("->%d", curr->data);
curr = curr->link;
}
return 0;
}
复杂度分析
- 时间复杂度： 𝑂(𝑚+𝑛) ，初始化辅助数组时间为 𝑂(𝑛) ，只需要遍历一次链表，时间为 𝑂(𝑚) 。
- 空间复杂度： 𝑂(𝑛) ，辅助数组空间为 𝑂(𝑛) 。
C++代码如下（含测试用例）：
#include <iostream>
#include <vector>
using namespace std;
struct ListNode {
int data;
ListNode *link;
};
ListNode* deleteDuplicates(ListNode* head, int n) {
vector<int>st(n + 1);
ListNode *prev = head;
ListNode *curr = head->link;
while (curr) {
if (st[abs(curr->data)]) {
prev->link = curr->link;
ListNode *temp = curr;
curr = curr->link;
delete temp;
} else {
st[abs(curr->data)] = 1;
prev = prev->link;
curr = curr->link;
}
}
return head;
}
ListNode* createLinkedList(vector<int> nums) {
ListNode* head = new ListNode();
ListNode* tail = head;
for (int i = 0; i < nums.size(); i++) {
ListNode* node = new ListNode();
node->data = nums[i];
node->link = nullptr;
tail->link = node;
tail = tail->link;
}
return head;
}
int main(int argc, const char * argv[]) {
vector<int>nums{21, -15, -15, -15, -7, 15, 15};
ListNode* head = createLinkedList(nums);
ListNode* newhead = deleteDuplicates(head, 32);
ListNode* curr = newhead->link;
cout << "head";
while (curr) {
cout << "->" << curr->data;
curr = curr->link;
}
return 0;
}
复杂度分析
- 时间复杂度： 𝑂(𝑚+𝑛) ，初始化辅助数组时间为 𝑂(𝑛) ，只需要遍历一次链表，时间为 𝑂(𝑚) 。
- 空间复杂度： 𝑂(𝑛) ，辅助数组空间为 𝑂(𝑛) 。
虽然C++的标准函数库提供了具有散列表功能的数据结构如unordered_set和unordered_map，但首选仍然是用数组代替散列表，unordered_set和unordered_map不到迫不得已的情况不考虑使用，散列表适用于元素稀疏离散或元素范围未知的情况。C语言没有提过散列表，可以采用三方开源uthash，可参考C语言哈希表uthash的使用方法详解（附下载链接）。
C代码如下（含测试用例）：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "uthash.h"
struct ListNode {
char data;
struct ListNode* link;
};
struct hashTable {
int key;
int val;
UT_hash_handle hh;
};
struct hashTable* hashtable;
struct hashTable* find(int ikey) {
struct hashTable* tmp;
HASH_FIND_INT(hashtable, &ikey, tmp);
return tmp;
}
void insert(int ikey, int ival) {
struct hashTable* it = find(ikey);
if (it == NULL) {
struct hashTable* tmp = malloc(sizeof(struct hashTable));
tmp->key = ikey, tmp->val = ival;
HASH_ADD_INT(hashtable, key, tmp);
} else {
it->val = ival;
}
}
struct ListNode *deleteDuplicates(struct ListNode* head) {
hashtable = NULL;
struct ListNode *prev = head;
struct ListNode *curr = head->link;
while (curr) {
struct hashTable *it = find(abs(curr->data));
if (it != NULL) {
prev->link = curr->link;
struct ListNode *temp = curr;
curr = curr->link;
free(temp);
} else {
insert(abs(curr->data), 1);
prev = prev->link;
curr = curr->link;
}
}
return head;
}
struct ListNode* createLinkedList(int *a, int n) {
struct ListNode* head = (struct ListNode *)malloc(sizeof(struct ListNode));
struct ListNode* tail = head;
for (int i = 0; i < n; i++) {
struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
node->data = a[i];
node->link = NULL;
tail->link = node;
tail = tail->link;
}
return head;
}
int main(int argc, const char * argv[]) {
int a[] = {21, -15, -15, -7, 15};
struct ListNode* head = createLinkedList(a, 5);
struct ListNode* newhead = deleteDuplicates(head);
struct ListNode* curr = head->link;
printf("head");
while (curr != NULL) {
printf("->%d", curr->data);
curr = curr->link;
}
return 0;
}
C++代码如下（含测试用例）：
#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;
struct ListNode {
int data;
ListNode *link;
};
ListNode* deleteDuplicates(ListNode* head) {
unordered_set<int>st;
ListNode *prev = head;
ListNode *curr = head->link;
while (curr) {
if (st.count(abs(curr->data))) {
prev->link = curr->link;
ListNode *temp = curr;
curr = curr->link;
delete temp;
} else {
st.insert(abs(curr->data));
prev = prev->link;
curr = curr->link;
}
}
return head;
}
ListNode* createLinkedList(vector<int> nums) {
ListNode* head = new ListNode();
ListNode* tail = head;
for (int i = 0; i < nums.size(); i++) {
ListNode* node = new ListNode();
node->data = nums[i];
node->link = nullptr;
tail->link = node;
tail = tail->link;
}
return head;
}
int main(int argc, const char * argv[]) {
vector<int>nums{21, -15, -15, -15, -7, 15, 15};
ListNode* head = createLinkedList(nums);
ListNode* newhead = deleteDuplicates(head);
ListNode* curr = newhead->link;
cout << "head";
while (curr) {
cout << "->" << curr->data;
curr = curr->link;
}
return 0;
}
复杂度分析
- 时间复杂度： 𝑂(𝑚) ，只需要遍历一次链表。
- 空间复杂度： 𝑂(𝑚) ，辅助散列表空间为 𝑂(𝑚) 。
评：这道题和力扣83. 删除排序链表中的重复元素非常相似，但是命题组在此基础上进行了改编，加大了难度。
2016¶
Note
43题:已知由 𝑛(𝑛≥2) 个正整数构成的集合 𝐴={𝑎𝑘|0≤𝑘<𝑛} ，将其划分为两个不相交的子集 𝐴1 和 𝐴2 ，元素个数分别是 𝑛1 和 𝑛2 ， 𝐴1 和 𝐴2 中元素之和分别为 𝑆1 和 𝑆2 。设计一个尽可能高效的划分算法，满足 |𝑛1−𝑛2| 最小且 |𝑆1−𝑆2| 最大。要求：
⑴ 给出算法的基本设计思想。
⑵ 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
⑶ 说明你所设计算法的时间复杂度和空间复杂度。
本题考察划分数组，用快速排序或者选择算法在中位数处进行划分。快速排序和选择算法都属于经典算法，《算法导论》对两者进行了非常详细的说明。
题源判定：命题组原创
题目难度：⭐️⭐️⭐️
解答：
由于 |𝑛1−𝑛2|≥0 恒成立，要使得 |𝑛1−𝑛2| 最小，所以
- 当 𝑛 为偶数时， |𝑛1−𝑛2| 最小值为 0 。
- 当 𝑛 为奇数时， |𝑛1−𝑛2| 最小值为 1 。
又要求 |𝑆1−𝑆2| 最大，所有数均为正数，假设 𝑆1≤𝑆2 ，有
- 当 𝑛 为偶数时， 𝑆1 为较小的 𝑛/2 个数的和， 𝑆2 为较大的 𝑛/2 个数的和。
- 当 𝑛 为奇数时， 𝑆1 为较小的 ⌊𝑛/2⌋ 个数的和， 𝑆2 为较大的 ⌈𝑛/2⌉ 个数的和。
综上， 𝑆1 为较小的 ⌊𝑛/2⌋ 个数的和， 𝑆2 为较大的 ⌈𝑛/2⌉ 个数的和。
方法一：快速排序
既然如此，如何获得较小的 ⌊𝑛/2⌋ 个数呢，我们很容易想到将 𝑛 个数进行排序，𝑆1 为前的 ⌊𝑛/2⌋ 个数的和， 𝑆2 为后的 ⌈𝑛/2⌉ 个数的和。
通常情况下我们采用快速排序处理排序问题。
C代码如下（含测试用例）：
#include <stdio.h>
#include <stdlib.h>
void swap(int *a, int i, int j){
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
int partition(int *a, int p, int r) {
int x = a[r];
int i = p - 1;
for (int j = p; j < r; ++j) {
if (a[j] <= x) {
++i;
swap(a, i, j);
}
}
swap(a, i + 1, r);
return i + 1;
}
int randomized_partition(int *a, int p, int r) {
int i = rand() % (r - p + 1) + p; // 随机选一个作为主元
swap(a, r, i);
return partition(a, p, r);
}
void randomized_quicksort(int *a, int p, int r) {
if (p < r) {
int q = randomized_partition(a, p, r);
randomized_quicksort(a, p, q - 1);
randomized_quicksort(a, q + 1, r);
}
}
int maxDifference(int *a, int n) {
randomized_partition(a, 0, n - 1);
int s1 = 0;
for (int i = 0; i < n / 2; ++i) {
s1 += a[i];
}
int s2 = 0;
for (int i = n / 2; i < n; ++i) {
s2 += a[i];
}
return s2 - s1;
}
int main(int argc, const char * argv[]) {
int a[5] = {30, 41, 9, 2, 17};
int res = maxDifference(a, 5);
printf("%d", res);
return 0;
}
复杂度分析：
- 时间复杂度： 𝑂(𝑛log𝑛) 。
- 空间复杂度： 𝑂(log𝑛) ，平均情况下递归栈深度为 𝑂(log𝑛) 。
个人评分：10分，本方法为暴力解法，时间复杂度和空间复杂度均为有较大优化空间。
参考《算法导论》相关章节如下：
方法二：选择算法
基于比较的排序算法的运行时间下界为 Ω(𝑛log𝑛) ，那么有没有更优秀的算法处理这个问题呢？答案是有，其实我们并不需要对数组进行完全排序，我们只需要利用快速排序的划分数组算法将数组划分为小于枢轴的部分和大于枢轴的部分，即选择算法。对比快速排序算法和选择算法，快速排序算法需要对所有分支进行递归，选择算法仅需要对包含目标元素的分支进行递归。
通常采用随机化选择算法RANDOMIZED-SELECT。
递归版
C代码如下（含测试用例）：
#include <stdio.h>
#include <stdlib.h>
void swap(int *a, int i, int j){
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
int partition(int *a, int p, int r) {
int x = a[r];
int i = p - 1;
for (int j = p; j < r; ++j) {
if (a[j] <= x) {
++i;
swap(a, i, j);
}
}
swap(a, i + 1, r);
return i + 1;
}
int randomized_partition(int *a, int p, int r) {
int i = rand() % (r - p + 1) + p; // 随机选一个作为主元
swap(a, r, i);
return partition(a, p, r);
}
void randomized_select(int *a, int p, int r, int i) {
if (p == r) {
return;
}
int q = randomized_partition(a, p, r);
int k = q - p + 1;
if (i == k) {
return;
} else if (i < k) {
randomized_select(a, p, q - 1, i);
} else {
randomized_select(a, q + 1, r, i - k);
}
}
int maxDifference(int *a, int n) {
randomized_select(a, 0, n - 1, n / 2);
int s1 = 0;
for (int i = 0; i < n / 2; ++i) {
s1 += a[i];
}
int s2 = 0;
for (int i = n / 2; i < n; ++i) {
s2 += a[i];
}
return s2 - s1;
}
int main(int argc, const char * argv[]) {
int a[5] = {30, 41, 9, 2, 17};
int res = maxDifference(a, 5);
printf("%d", res);
return 0;
}
复杂度分析：
- 时间复杂度： 𝑂(𝑛) 。
- 空间复杂度： 𝑂(log𝑛) ，平均情况下递归栈深度为 𝑂(log𝑛) 。
迭代版
C代码如下（含测试用例）：
#include <stdio.h>
#include <stdlib.h>
void swap(int *a, int i, int j){
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
int partition(int *a, int p, int r) {
int x = a[r];
int i = p - 1;
for (int j = p; j < r; ++j) {
if (a[j] <= x) {
++i;
swap(a, i, j);
}
}
swap(a, i + 1, r);
return i + 1;
}
int randomized_partition(int *a, int p, int r) {
int i = rand() % (r - p + 1) + p; // 随机选一个作为主元
swap(a, r, i);
return partition(a, p, r);
}
void randomized_select(int *a, int p, int r, int i) {
int q, k;
while (1) {
q = partition(a, p, r);
k = q - p + 1;
if (i == k) {
return;
} else if (i < k) {
r = q - 1;
} else {
p = q + 1;
i = i - k;
}
}
}
int maxDifference(int *a, int n) {
randomized_select(a, 0, n - 1, n / 2);
int s1 = 0;
for (int i = 0; i < n / 2; ++i) {
s1 += a[i];
}
int s2 = 0;
for (int i = n / 2; i < n; ++i) {
s2 += a[i];
}
return s2 - s1;
}
int main(int argc, const char * argv[]) {
int a[5] = {30, 41, 9, 2, 17};
int res = maxDifference(a, 5);
printf("%d", res);
return 0;
}
复杂度分析：
- 时间复杂度： 𝑂(𝑛) 。
- 空间复杂度： 𝑂(1) ，使用了常数个辅助变量。
个人评分：15分，时间复杂度和空间复杂度均为最优。
参考《算法导论》相关章节如下：
这里RANDOMIZED-SELECT也可以进一步优化为最坏情况下时间复杂度为 𝑂(𝑛) 的SELECT算法。但是难度过大，考场上不推荐使用。
参考《算法导论》相关章节如下：
选择算法也是TopK问题的最优解，2023年题42对TopK问题进行了考察。
2017¶
Note
41题:请设计一个算法，将给定的表达式树（二叉树）转换为等价的中缀表达式（通过括号反映操作符的计算次序）并输出。例如，当下列两棵表达式树作为算法输入时：
输出的中缀表达式分别为 (𝑎+𝑏)∗(𝑐∗(−𝑑)) 和 (𝑎∗𝑏)+(−(𝑐−𝑑)) 。
二叉树结点的定义如下：
typedef struct node{
char data[10]; // 存储操作数或操作符
struct node *left, *right;
}BTree;
要求：
⑴ 给出算法的基本设计思想。
⑵ 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
本题考察深度优先搜索和递归。
PAT甲级 1130 Infix Expression
相似度：90%，真题的二叉树用二叉链表存储，该题用数组存储的三元组。
题源判定：PAT，这道题也可以视为命题组自命题，因为《数据结构（C语言版）》中也提到了表达式树的概念。因为PAT给出了相似的OJ，而且浙江大学一直坚持考408，暂且把这道题的题源归为PAT。
AcWing 3765. 表达式树（来源：2017年全国硕士研究生招生考试）提供了本题的 OJ。
题目难度：⭐️⭐️⭐️
解答：
题目要求输出中缀表达式，对应表达式树（二叉树）的中序遍历序列。但本题难点在于要输出左右括号，所以也融合了二叉树的前序遍历和后序遍历，二叉树的前序遍历、中序遍历、后序遍历本质都是深度优先搜索。
方法一：深度优先搜索
递归遍历
C代码如下（含测试用例）：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node{
char data[10]; // 存储操作数或操作符
struct node *left, *right;
}BTree;
void dfs(BTree* root) {
if (root == NULL) return;
if (root->left == NULL && root->right == NULL) { // 如果只有一个数那么不需要加括号
printf("%s", root->data);
} else {
printf("(");
dfs(root->left);
printf("%s", root->data);
dfs(root->right);
printf(")");
}
}
void expressionTree(BTree* root) {
if(root == NULL) return;
dfs(root->left);
printf("%s", root->data);
dfs(root->right);
return;
}
BTree *createBinaryTree(char a[][10], int n) {
if (strcmp(a[0], "null") == 0) {
return NULL;
}
int i = 0;
BTree *root = (struct node*)malloc(sizeof(struct node));
strcpy(root->data, a[i++]);
root->left = NULL;
root->right = NULL;
struct node** que = (struct node**)malloc(sizeof(struct node*));
int front = 0, rear = 0;
BTree *curr = root;
que[rear++] = curr;
while (front < rear && i < n) {
curr = que[front++];
for (int j = 0; j < 2 && i < n; j++, i++) {
if (strcmp(a[i], "null") != 0) {
if (j == 0) {
curr->left = (struct node*)malloc(sizeof(struct node));
strcpy(curr->left->data, a[i]);
curr->left->left = NULL;
curr->left->right = NULL;
que[rear++] = curr->left;
} else {
curr->right = (struct node*)malloc(sizeof(struct node));
strcpy(curr->right->data, a[i]);
curr->right->left = NULL;
curr->right->right = NULL;
que[rear++] = curr->right;
}
}
}
}
return root;
}
int main() {
char a[][10] = {"*", "+", "*", "a", "b", "c", "-", "null", "null", "null", "null", "null", "null", "null", "d"};
expressionTree(createBinaryTree(a, 15));
return 0;
}
有同学一定要问，为什么expressionTree中要左右子树分两次进行深度优先搜索，而不直接写成：
这样写的话整个表达式最外层会多加一对括号，所以写代码思维要非常缜密才行。
王道给出的参考答案里增加了deep变量维护结点深度，初始化为1，只有当deep > 1时才能添加括号，这样可以直接从根结点开始进行递归，也是很好的技巧。deep是形容词，depth才是名词，这里用名词更加合适。
复杂度分析
- 时间复杂度： 𝑂(𝑛) ，其中 𝑛 为二叉树的结点个数。二叉树的每个结点最多被访问三次，因此时间复杂度为 𝑂(𝑛) 。
- 空间复杂度： 𝑂(𝑛) ，其中 𝑛 为二叉树的结点个数。递归栈最深为 𝑛 ，因此需要额外的 𝑂(𝑛) 的空间。
由于表达式要嵌套括号，相当于同时融合了前序遍历、中序遍历、后序遍历。当然深度优先搜索递归版也可以借助栈修改为迭代版，有兴趣的同学可以尝试下。
深度优先搜索有括号化定理。本题非常形象的展示了该定理。
注：参考AcWing3765. 表达式树。
拓展：当然由表达式树推导中缀表达式难度较低，反过来由中缀表达式推导表达式树则难度较大，感兴趣的同学可以练习下力扣1597. 根据中缀表达式构造二叉表达式树，本题为困难难度的题。
计算机一般用后缀表达式进行求值，感兴趣的同学可以练习下力扣150. 逆波兰表达式求值。
2018¶
Note
41题 : 给定一个含 𝑛(𝑛≥1) 个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5, 3, 2, 3}中未出现的最小正整数是1；数组{1, 2, 3}中未出现的最小正整数是4。要求：
⑴ 给出算法的基本设计思想。
⑵ 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
⑶ 说明你所设计算法的时间复杂度和空间复杂度。
本题深入考察了散列表的使用。
力扣 41. 缺失的第一个正数
相似度：100%。
题源判定：LeetCode
AcWing 3820. 未出现过的最小正整数（来源：2019年全国硕士研究生招生考试）提供了本题的 OJ。
题目难度：⭐️⭐️⭐️⭐️
解答：
可参考力扣41. 缺失的第一个正数
方法一：哈希表
本方法为暴力解。
哈希表是一个可以支持快速查找的数据结构：给定一个元素，我们可以在 𝑂(1) 的时间查找该元素是否在哈希表中。
C代码如下（含测试用例）：
#include <stdio.h>
#include <stdlib.h>
#include "uthash.h"
struct hashTable {
int key;
int val;
UT_hash_handle hh;
};
struct hashTable* hashtable;
struct hashTable* find(int ikey) {
struct hashTable* tmp;
HASH_FIND_INT(hashtable, &ikey, tmp);
return tmp;
}
void insert(int ikey, int ival) {
struct hashTable* it = find(ikey);
if (it == NULL) {
struct hashTable* tmp = malloc(sizeof(struct hashTable));
tmp->key = ikey;
tmp->val = ival;
HASH_ADD_INT(hashtable, key, tmp);
} else {
it->val = ival;
}
}
int firstMissingPositive(int* nums, int numsSize) {
for (int i = 0; i < numsSize; i++) {
insert(nums[i], 1);
}
for (int i = 1; i <= numsSize; i++) {
struct hashTable* it = find(i);
if (it == NULL) {
return i;
}
}
return numsSize + 1;
}
int main() {
int a[] = {-5, 3, 2, 3};
int miss = firstMissingPositive(a, 4);
printf("%d", miss);
return 0;
}
C++代码如下（含测试用例）：
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
unordered_set<int> st;
for (int num : nums) {
st.insert(num);
}
for (int i = 1; i <= n; ++i) {
if (!st.count(i)){
return i;
}
}
return n + 1;
}
int main(int argc, const char * argv[]) {
vector<int> a = {-5, 3, 2, 3};
int miss = firstMissingPositive(a);
cout << miss;
return 0;
}
这里可以用数组作为哈希表进行优化，由于结果 𝑥 一定满足 1≤𝑥≤𝑛+1 ，所以只需要记录值在这个范围中的元素，修改如下：
C代码如下（含测试用例）：
#include <stdio.h>
#include <string.h>
int firstMissingPositive(int* a, int n){
int f[n + 1];
memset(f, 0, sizeof(f));
for (int i = 0; i < n; i++) {
if (a[i] > 0 && a[i] <= n) {
f[a[i]] = 1;
}
}
for (int i = 1; i <= n; i++) {
if (f[i] == 0) {
return i;
}
}
return n + 1;
}
int main() {
int a[] = {-5, 3, 2, 3};
int miss = firstMissingPositive(a, 4);
printf("%d", miss);
return 0;
}
C++代码如下（含测试用例）：
#include <iostream>
#include <vector>
using namespace std;
int firstMissingPositive(vector<int>& nums) {
int n = (int) nums.size();
vector<bool> flag(n + 1, false);
for (int num: nums) {
if (num > 0 && num <= n) {
flag[num] = true;
}
}
for (int i = 1; i <= n; i++) { // 从1开始遍历flag数组
if (!flag[i]) {
return i; // 第一个位置为false的就是缺失的最小正整数
}
}
return n + 1; // 位置均为true，没有缺失正数返回n+1
}
int main(int argc, const char * argv[]) {
vector<int> a = {-5, 3, 2, 3};
int miss = firstMissingPositive(a);
cout << miss;
return 0;
}
复杂度分析
- 时间复杂度： 𝑂(𝑛) 。
- 空间复杂度： 𝑂(𝑛) ，需要开辟大小为 𝑂(𝑛) 的辅助哈希表。
方法二：原地哈希
这个思路非常巧妙，用负号标记元素存在。将数组的下标假想为哈希表的键。
算法的流程如下：
- 我们将数组中所有小于或等于 0 的数修改为 𝑛+1 ；
- 我们遍历数组中的每一个数 𝑥 ，它可能已经被打了标记，因此原本对应的数为 |𝑥| 。如果 |𝑥|∈[1,𝑛] ，那么我们给数组中的第 |𝑥|−1 个位置的数添加一个负号。注意如果它已经有负号，不需要重复添加；
- 在遍历完成之后，如果数组中的每一个数都是负数，那么答案是 𝑛+1 ，否则答案是第一个正数的位置加 1 。
C代码如下（含测试用例）：
#include <stdio.h>
int firstMissingPositive(int* nums, int numsSize) {
for (int i = 0; i < numsSize; ++i) {
if (nums[i] <= 0) {
nums[i] = numsSize + 1;
}
}
for (int i = 0; i < numsSize; ++i) {
int num = abs(nums[i]);
if (num <= numsSize) {
nums[num - 1] = -abs(nums[num - 1]);
}
}
for (int i = 0; i < numsSize; ++i) {
if (nums[i] > 0) {
return i + 1;
}
}
return numsSize + 1;
}
int main() {
int a[] = {-5, 3, 2, 3};
int miss = firstMissingPositive(a, 4);
printf("%d", miss);
return 0;
}
C++代码如下（含测试用例）：
#include <iostream>
#include <vector>
using namespace std;
int firstMissingPositive(vector<int>& nums) {
int n = (int)nums.size();
for (int& num : nums) {
if (num <= 0) {
num = n + 1; //越界数字处理
}
}
for (int i = 0; i < n; ++i) {
int num = abs(nums[i]);
if (num <= n) { //合格的数字
nums[num - 1] = -abs(nums[num - 1]); //-标记,正确数字对应的位置
}
}
for (int i = 0; i < n; ++i) { //找到第一个为正数的位置
if (nums[i] > 0) {
return i + 1; //位置下标+1为缺失数
}
}
return n+1;
}
int main(int argc, const char * argv[]) {
vector<int> a = {-5, 3, 2, 3};
int miss = firstMissingPositive(a);
cout << miss;
return 0;
}
复杂度分析
- 时间复杂度： 𝑂(𝑛) 。
- 空间复杂度： 𝑂(1) 。
方法三：置换
除了打标记以外，我们还可以使用置换的方法。
在恢复后，数组应当有{1, 2, ..., n}的形式，但其中有若干个位置上的数是错误的，每一个错误的位置就代表了一个缺失的正数。以{3, 4, -1, 1}为例，恢复后的数组应当为{1, -1, 3, 4}，我们就可以知道缺失的数为2。
由于每次的交换操作都会使得某一个数交换到正确的位置，因此交换的次数最多为 𝑛 ，整个方法的时间复杂度为 𝑂(𝑛) 。
C代码如下（含测试用例）：
#include <stdio.h>
int firstMissingPositive(int* nums, int numsSize) {
for (int i = 0; i < numsSize; ++i) {
while (nums[i] > 0 && nums[i] <= numsSize &&
nums[nums[i] - 1] != nums[i]) {
int t = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i], nums[i] = t;
}
}
for (int i = 0; i < numsSize; ++i) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return numsSize + 1;
}
int main() {
int a[] = {-5, 3, 2, 3};
int miss = firstMissingPositive(a, 4);
printf("%d", miss);
return 0;
}
C++代码如下（含测试用例）：
#include <iostream>
#include <vector>
using namespace std;
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n; ++i) {
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
swap(nums[nums[i] - 1], nums[i]);
}
}
for (int i = 0; i < n; ++i) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}
int main(int argc, const char * argv[]) {
vector<int> a = {-5, 3, 2, 3};
int miss = firstMissingPositive(a);
cout << miss;
return 0;
}
复杂度分析
- 时间复杂度： 𝑂(𝑛) 。
- 空间复杂度： 𝑂(1) 。
评：这道题力扣原题标记位困难，其实本题难在思维，代码并不复杂
2019¶
Note
41题: 设线性表 𝐿=(𝑎1,𝑎2,𝑎3,…,𝑎𝑛−2,𝑎𝑛−1,𝑎𝑛) 采用带头结点的单链表保存，链表中的结点定义如下：
请设计一个空间复杂度为 𝑂(1)且时间上尽可能高效的算法，重新排列 𝐿 中的各结点，得到线性表 𝐿′=(𝑎1,𝑎𝑛,𝑎2,𝑎𝑛−1,𝑎3,𝑎𝑛−2,…) 。要求：
⑴ 给出算法的基本设计思想。
⑵ 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
⑶ 说明你所设计算法的时间复杂度。
本题深入考察了链表指针的使用，包括反转链表，快慢指针。
力扣 143. 重排链表
相似度：100%。
题源判定：LeetCode
AcWing 3757. 重排链表（来源：2019年全国硕士研究生招生考试）提供了本题的 OJ。
题目难度：⭐️⭐️⭐️
解答：
注意：题目中单链表带头结点，头结点不存储关键字。
思路一：开辟一个长度为 𝑛 的辅助数组，将所有结点存入，然后直接操作数组下标，重新构建链表。该算法空间复杂度为 𝑂(𝑛) ，但是这里题目已经明确要求设计一个空间复杂度为 𝑂(1) 的算法，所以不能使用。
所以本题只能使用一个原地算法。目前主流的解法如下：
寻找链表中点 + 反转链表 + 合并链表
目标链表即为将原链表的左半端和反转后的右半端合并后的结果。这样可以分为三步。
第一步：找到原链表的中点，本题为下中位数点 𝑎⌈𝑛/2⌉ ，即第 ⌈𝑛/2⌉ 个结点，（参考力扣 876. 链表的中间结点，但注意这道题的中间结点和本题的中间结点的定义不同，这道题要求找第 ⌈(𝑛+1)/2⌉ 个结点，即上中位数点。）
为什么是找下中位数点，这道题将链表分成两段，左半段为 𝑎1,𝑎2,…,𝑎⌈𝑛/2⌉ ，右半段为 𝑎⌈𝑛/2⌉+1,𝑎⌈𝑛/2⌉+2,…,𝑎𝑛 ，这样能够满足当 𝑛 为偶数时，左半段结点个数和右半段结点个数相等，当 𝑛 为奇数时，左半段结点个数比右半段结点个数多 1。为什么要求当 𝑛 为奇数时左半段结点个数比右半段结点个数多 1，因为第一个元素 𝑎1 是左半段元素，这样交替后最后一个元素一定是左半段的元素，恰巧比右半段多出一个。
使用快慢指针可以方便找出链表中位于中位数位置的结点，该步时间复杂度 𝑂(𝑛) 。
第二步：将原链表的右半段反转。（参考力扣 206. 反转链表。）
反转链表有三种方法，递归法，迭代法，头插法。这三种方法中，迭代法是最优解。
这里使用迭代法实现链表的反转，该步时间复杂度 𝑂(𝑛) 。
第三步：将两条链表合并。
因为两链表长度相差不超过一，交叉合并，该步时间复杂度 𝑂(𝑛) 。
综上，该算法的时间复杂度为 𝑂(𝑛)+𝑂(𝑛)+𝑂(𝑛)=𝑂(𝑛) 。
C代码如下（含测试用例）：
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node *next;
} NODE;
void reorderList(NODE* h) {
NODE *p, *q, *r, *s;
// 第一步：寻找h中间结点
p = q = h;
while (q->next != NULL) {
p = p->next;
q = q->next;
if (q->next != NULL) {
q = q->next;
}
}
q = p->next;
p->next = NULL;
// 第二步：将链表后半段反转
while (q != NULL) {
r = q->next;
q->next = p->next;
p->next = q;
q = r;
}
// 第三步：合并链表
s = h->next;
q = p->next;
p->next = NULL;
while (q != NULL) {
r = q->next;
q->next = s->next;
s->next = q;
s = q->next;
q = r;
}
}
NODE* createLinkedList(int *a, int n) {
NODE* head = (NODE *)malloc(sizeof(struct node));
NODE* tail = head;
for (int i = 0; i < n; i++) {
NODE* p = (NODE *)malloc(sizeof(struct node));
p->data = a[i];
p->next = NULL;
tail->next = p;
tail = tail->next;
}
return head;
}
int main() {
int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
NODE* head = createLinkedList(a, 9);
reorderList(head);
NODE* curr = head;
printf("head");
while (curr != NULL) {
printf("->%d", curr->data);
curr = curr->next;
}
return 0;
}
说实话，标准答案的指针利用率非常高，缺点也很明显，可读性很差。
这道题实际上是三个基础算法的组合，本人把三段代码拆分三个方法。
C代码如下（含测试用例）：
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node *next;
} NODE;
NODE* middleNode(NODE* head) {
NODE* slow = head;
NODE* fast = head;
while (fast->next != NULL && fast->next->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
NODE* reverseList(NODE* head) {
NODE* prev = NULL;
NODE* curr = head;
while (curr != NULL) {
NODE* nextTemp = curr->next;
curr->next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
void mergeList(NODE* l1, NODE* l2) {
NODE* l1_tmp;
NODE* l2_tmp;
while (l1 != NULL && l2 != NULL) {
l1_tmp = l1->next;
l2_tmp = l2->next;
l1->next = l2;
l1 = l1_tmp;
l2->next = l1;
l2 = l2_tmp;
}
}
void reorderList(NODE* head) {
if (head == NULL || head->next == NULL) {
return;
}
NODE* mid = middleNode(head->next);
NODE* l1 = head->next;
NODE* l2 = mid->next;
mid->next = NULL;
l2 = reverseList(l2);
mergeList(l1, l2);
}
NODE* createLinkedList(int *a, int n) {
NODE* head = (NODE *)malloc(sizeof(struct node));
NODE* tail = head;
for (int i = 0; i < n; i++) {
NODE* p = (NODE *)malloc(sizeof(struct node));
p->data = a[i];
p->next = NULL;
tail->next = p;
tail = tail->next;
}
return head;
}
int main() {
int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
NODE* head = createLinkedList(a, 9);
reorderList(head);
NODE* curr = head;
printf("head");
while (curr != NULL) {
printf("->%d", curr->data);
curr = curr->next;
}
return 0;
}
C++代码如下（含测试用例）：
#include <iostream>
using namespace std;
typedef struct node {
int data;
struct node *next;
} NODE;
NODE* middleNode(NODE* head) {
NODE* slow = head;
NODE* fast = head;
while (fast->next != nullptr && fast->next->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
NODE* reverseList(NODE* head) {
NODE* prev = nullptr;
NODE* curr = head;
while (curr != nullptr) {
NODE* nextTemp = curr->next;
curr->next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
void mergeList(NODE* l1, NODE* l2) {
NODE* l1_tmp;
NODE* l2_tmp;
while (l1 != nullptr && l2 != nullptr) {
l1_tmp = l1->next;
l2_tmp = l2->next;
l1->next = l2;
l1 = l1_tmp;
l2->next = l1;
l2 = l2_tmp;
}
}
void reorderList(NODE* head) {
if (head == nullptr || head->next == nullptr) {
return;
}
NODE* mid = middleNode(head->next);
NODE* l1 = head->next;
NODE* l2 = mid->next;
mid->next = nullptr;
l2 = reverseList(l2);
mergeList(l1, l2);
}
NODE* createLinkedList(int *a, int n) {
NODE* head = new NODE();
NODE* tail = head;
for (int i = 0; i < n; i++) {
NODE* p = new NODE();
p->data = a[i];
p->next = nullptr;
tail->next = p;
tail = tail->next;
}
return head;
}
int main() {
int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
NODE* head = createLinkedList(a, 9);
reorderList(head);
NODE* curr = head;
cout << "head";
while (curr != nullptr) {
cout << "->"<< curr->data;
curr = curr->next;
}
return 0;
}
复杂度分析
- 时间复杂度： 𝑂(𝑛) 。
- 空间复杂度： 𝑂(1) 。
注：参考力扣143. 重排链表。
2020¶
Note
41题 : 定义三元组 (𝑎,𝑏,𝑐) （ 𝑎,𝑏,𝑐 均为正数）的距离 𝐷=|𝑎−𝑏|+|𝑏−𝑐|+|𝑐−𝑎| 。给定 3 个非空整数集合 𝑆1 、 𝑆2 和 𝑆3 ，按升序分别存储在 3 个数组中。请设计一个尽可能高效的算法，让算并输出所有可能的三元组 (𝑎,𝑏,𝑐) （其中 𝑎∈𝑆1,𝑏∈𝑆2,𝑐∈𝑆3 ）中的最小距离。例如 𝑆1={−1,0,9} ， 𝑆2={−25,−10,10,11} ， 𝑆3={2,9,17,30,41} ，则最小距离为 2 ，相应的三元组为 (9,10,9) 。要求：
⑴ 给出算法的基本设计思想。
⑵ 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
⑶ 说明你所设计算法的时间复杂度和空间复杂度。
本题深入考察了滑动窗口。这里为同向三指针，求最左和最右指针的最小距离，可以理解为广义的求滑动窗口最小值。
力扣 632. 最小区间
相似度：100%，考察内容本质上一致，只不过题目的换了一种表述。
AcWing 3874. 三元组的最小距离（来源：2020年全国硕士研究生招生考试）提供了本题的 OJ。
题源判定：LeetCode
题目难度：⭐️⭐️⭐️⭐️⭐️
解答：
方法一：暴力法
用i、j、k三个指针分别表示当前指向数组集合 𝑆1 、 𝑆2 和 𝑆3 中的位置，枚举所有的三元组，取所有三元组中的最小距离。
C代码如下（含测试用例）：
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int findMinDist(int s1[], int s2[], int s3[], int n1, int n2, int n3) {
int min_dist = INT_MAX;
int dist;
for (int i = 0; i < n1; i++) {
for (int j = 0; j < n2; j++) {
for (int k = 0; k < n3; k++) {
dist = abs(s1[i] - s2[j]) + abs(s2[j] - s3[k]) + abs(s3[k] - s1[i]);
if (dist < min_dist) {
min_dist = dist;
}
}
}
}
return min_dist;
}
int main(int argc, const char * argv[]) {
int s1[3] = {-1, 0, 9};
int s2[4] = {-25, -10, 10, 11};
int s3[5] = {2, 9, 17, 30, 41};
int ans = findMinDist(s1, s2, s3, 3, 4, 5);
printf("%d\n", ans);
return 0;
}
复杂度分析
- 时间复杂度： 𝑂(𝑛1𝑛2𝑛3) ，其中 𝑛1、𝑛2 和 𝑛3 分别为S1、S2和S3的长度。
- 空间复杂度： 𝑂(1) ，中间过程额外需要常数个变量。
如果用暴力法应该能拿到一半多一点的分，也就是本题13分能拿到7-8分。
方法二：同向多指针（滑动窗口变体）
这道题难度非常大，称为408史上第二难算法题毫不过分，本题需要用到多指针或指针数组。
使用i、j、k三个指针分别指向三个数组的首个元素，每次移动三个指针中指向元素最小的指针（三个指针可能交替移动），移动后检查有没有产生更短的距离。这里为同向三指针，将所有元素放到一个数轴上，求最左和最右指针的最小距离，可以理解为广义的求滑动窗口最小值。
C代码如下（含测试用例）：
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int findMinDist(int s1[], int s2[], int s3[], int n1, int n2, int n3) {
int min_dist = INT_MAX;
int dist;
int i = 0, j = 0, k = 0;
while (i < n1 && j < n2 && k < n3) {
dist = abs(s1[i] - s2[j]) + abs(s2[j] - s3[k]) + abs(s3[k] - s1[i]);
if (dist < min_dist) {
min_dist = dist;
}
if (s1[i] < s2[j]) {
if (s1[i] < s3[k]) { // s1[i]
i++;
} else { // s3[k]
k++;
}
} else {
if (s2[j] < s3[k]) { // s2[j]
j++;
} else { // s3[k]
k++;
}
}
}
return min_dist;
}
int main(int argc, const char * argv[]) {
int s1[3] = {-1, 0, 9};
int s2[4] = {-25, -10, 10, 11};
int s3[5] = {2, 9, 17, 30, 41};
int ans = findMinDist(s1, s2, s3, 3, 4, 5);
printf("%d\n", ans);
return 0;
}
复杂度分析
- 时间复杂度： 𝑂(𝑛1+𝑛2+𝑛3) ，其中 𝑛1、𝑛2 和 𝑛3 分别为S1、S2和S3的长度。
- 空间复杂度： 𝑂(1) ，中间过程额外需要常数个变量。
注：参考AcWing3874. 三元组的最小距离。
如果非要给这道题在力扣上找一道类似的题，就是23. 合并K个升序链表，有一种办法是构造K个指针，或者一个长度为K的指针数组，刚开始分别指向每条链表中第一个元素，每次取出K个元素中最小的元素，并移动指针。但是这道题有很多更好的解法，这道题力扣标记为困难，2020年这道算法真题可以标记为困难也是毫无疑问的。
如果同学们对多指针感兴趣，可以练习一下力扣里这道题：264. 丑数 II 。
另外，滑动窗口更多是通过双指针进行考察，推荐练习力扣 3. 无重复字符的最长子串 、 219. 存在重复元素 II 和 643. 子数组最大平均数 I。
遇到这种题，考场上千万不要为了找出最优解花时间硬耗，暴力法先保分，就算你真的花了半小时一小时想出了最优解，后面大题来不及做，丢分更多，完全是得不偿失的事情。
2021¶
41题: 已知无向连通图G由顶点集V和边集E组成，|E| > 0，当G中度为奇数的顶点个数为不大于2的偶数时，G存在包含所有边且长度为|E|的路径（称为EL路径）。设图G采用邻接矩阵存储，类型定义如下:
typedef struct { // 图的定义
int numVertices, numEdges; // 图中实际的顶点数和边数
char VerticesList[MAXV]; // 顶点表，MAXV为已定义常量
int Edge[MAXV][MAXV]; // 邻接矩阵
}MGraph;
请设计算法int IsExistEL(MGraph G)，判断G是否存在EL路径，若存在，则返回1 ，否则返回0。要求:
⑴ 给出算法的基本设计思想。
⑵ 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
⑶ 说明你所设计算法的时间复杂度和空间复杂度。
本题考察度的定义和计数法。
PAT甲级 1126 Eulerian Path
相似度：95%，真题要求判断一个无向图中是否存在欧拉路径（即为欧拉图或半欧拉图），该题要求判断一个无向图是欧拉图、半欧拉图还是非欧拉图。
题源判定：PAT，这道题也可以视为命题组自命题，因为《数据结构（C语言版）》的最重要参考书《数据结构基础》中也提到了欧拉路径的概念。因为PAT给出了相似的OJ，而且浙江大学一直坚持考408，暂且把这道题的题源归为PAT。
题目难度：⭐️
解：
- 第一步：统计所有点的度。
- 第二步：统计所有点中度为奇数的点的个数。
- 第三步：检查度为奇数的点个数是否为0或者2。
这道题称为408史上最简单算法题毫不过分，只因为第一次考图就离谱的送分，一送还送15分，但我估计要送就送这么一次，以后的考生就没这么好运了。
⑵ 根据上述思路，C代码如下（含测试用例）：
#include <stdio.h>
#include <string.h>
#define MAXV 11
typedef struct { // 图的定义
int numVertices, numEdges; // 图中实际的顶点数和边数
char VerticesList[MAXV]; // 顶点表，MAXV为已定义常量
int Edge[MAXV][MAXV]; // 邻接矩阵
}MGraph;
int IsExistEL(MGraph G) {
int degrees[G.numVertices];
memset(degrees, 0, sizeof(degrees));
// 遍历无向图统计所有点的度
for (int i = 0; i < G.numVertices; i++) {
for (int j = 0; j < G.numVertices; j++) {
degrees[i] += G.Edge[i][j];
}
}
int count = 0;
// 遍历degrees数组统计度为奇数的点的个数
for (int i = 0; i < G.numVertices; i++) {
if (degrees[i] % 2 != 0) {
count++;
}
}
// 检查度为奇数的点个数是否为0或者2
if (count == 0 || count == 2) {
return 1; // 存在EL路径
} else {
return 0; // 不存在EL路径
}
}
int main() {
// 以图(a)为例
MGraph G;
G.numEdges = 6;
G.numVertices = 5;
memset(G.VerticesList, 0, sizeof(G.numVertices));
char V[5] = {'a', 'b', 'c', 'd', 'e'};
for (int i = 0; i < G.numVertices; i++) {
G.VerticesList[i] = V[i];
}
memset(G.Edge, 0, sizeof(G.numVertices));
int M[5][5] = {{0, 1, 0, 0, 1}, {1, 0, 1, 1, 0}, {0, 1, 0, 1, 0}, {0, 1, 1, 0, 1}, {1, 0, 0, 1, 0}};
for (int i = 0; i < G.numVertices; i++) {
for (int j = 0; j < G.numVertices; j++) {
G.Edge[i][j] = M[i][j];
}
}
if (IsExistEL(G)) {
printf("There is a Euler path. ");
} else {
printf("There is no Euler path. ");
}
return 0;
}
复杂度分析
- 时间复杂度： 𝑂(𝑛2) ，其中 𝑛 为图中点个数。因为需要遍历整个邻接矩阵，所以为 𝑂(𝑛2) 。
- 空间复杂度： 𝑂(𝑛) ，开辟了 𝑂(𝑛) 大小的辅助数组。
如果到这里就结束了，这道题也太简单了吧，明显需要进行优化。时间复杂度无法优化，我们考虑优化空间复杂度，去掉辅助数组，边遍历边统计。修改后C代码如下（含测试用例）：
#include <stdio.h>
#include <string.h>
#define MAXV 11
typedef struct { // 图的定义
int numVertices, numEdges; // 图中实际的顶点数和边数
char VerticesList[MAXV]; // 顶点表，MAXV为已定义常量
int Edge[MAXV][MAXV]; // 邻接矩阵
}MGraph;
int IsExistEL(MGraph G) {
int degree = 0;
int count = 0;
// 遍历无向图统计所有点的度
for (int i = 0; i < G.numVertices; i++) {
degree = 0; // 重置
// 计算点i的度
for (int j = 0; j < G.numVertices; j++) {
degree += G.Edge[i][j];
}
// 检查点i的度是否为奇数
if (degree % 2 != 0) {
count++;
}
}
// 检查度为奇数的点个数是否为0或者2
if (count == 0 || count == 2) {
return 1; // 存在EL路径
} else {
return 0; // 不存在EL路径
}
}
int main() {
// 以图(a)为例
MGraph G;
G.numEdges = 6;
G.numVertices = 5;
memset(G.VerticesList, 0, sizeof(G.numVertices));
char V[5] = {'a', 'b', 'c', 'd', 'e'};
for (int i = 0; i < G.numVertices; i++) {
G.VerticesList[i] = V[i];
}
memset(G.Edge, 0, sizeof(G.numVertices));
int M[5][5] = {{0, 1, 0, 0, 1}, {1, 0, 1, 1, 0}, {0, 1, 0, 1, 0}, {0, 1, 1, 0, 1}, {1, 0, 0, 1, 0}};
for (int i = 0; i < G.numVertices; i++) {
for (int j = 0; j < G.numVertices; j++) {
G.Edge[i][j] = M[i][j];
}
}
if (IsExistEL(G)) {
printf("There is a Euler path. ");
} else {
printf("There is no Euler path. ");
}
return 0;
}
复杂度分析
- 时间复杂度： 𝑂(𝑛2) ，其中 𝑛 为图中点个数。因为需要遍历整个邻接矩阵，所以为 𝑂(𝑛2) 。
- 空间复杂度： 𝑂(1) ，使用了常数个临时变量。
2022¶
41题 ：已知非空二叉树T的结点值均为正数，采用顺序存储方式保存，数据结构定义如下：
typedef struct { // MAX_SIZE为已定义常量
Elemtype SqBiTNode[MAX_SIZE]; // 保存二叉树结点值的数组
int ElemNum; // 实际占用的数组元素个数
}SqBiTree;
T中不存在的结点在数组SqBiTNode中用-1表示。例如，对于下图所示的两棵非空二叉树T1和T2：
请设计一个尽可能高效的算法，判定一棵采用这种方式存储的二叉树是否为二叉搜索树，若是，则返回true，否则，返回false，要求：
⑴ 给出算法的基本设计思想。
⑵ 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
本题考察二叉搜索树的性质。
力扣 98. 验证二叉搜索树。
相似度：90%，真题的二叉树用数组存储的静态二叉链表，该题用二叉链表存储。
PAT甲级 1043 Is It a Binary Search Tree
相似度：90%，真题的二叉树用数组存储的静态二叉链表，该题用数组存储的三元组。
题源判定：LeetCode
题目难度：⭐️⭐️
解答：
注意本题二叉树以静态数组的方式表示，数组起始下标为0。
先画出二叉树，然后将其填充为完全二叉树，按照层序遍历顺序填写编号：
如果根结点下标为0（适用于C/C++语言数组）有 ：
如果根结点下标为1，这时候题目会写明条件。
为了方便解答，结构体中的Elemtype默认为int。
方法一：递归
利用二叉搜索树的性质：设 𝑥 是二叉搜索树中的一个结点。如果𝑦是𝑥左子树中的一个结点，那么𝑦.𝑘𝑒𝑦≤𝑥.𝑘𝑒𝑦，如果𝑦是𝑥右子树中的一个结点，那么𝑦.𝑘𝑒𝑦≥𝑥.𝑘𝑒𝑦。
C代码如下（含测试用例）：
#include <stdio.h>
#include <string.h>
#include <limits.h>
#define MAX_SIZE 20011
#define false 0
#define true 1
typedef int bool;
typedef struct { // MAX_SIZE为已定义常量
int SqBiTNode[MAX_SIZE]; // 保存二叉树结点值的数组
int ElemNum; // 实际占用的数组元素个数
}SqBiTree;
bool helper(SqBiTree T, int i, long long lower, long long upper) {
if (i >= T.ElemNum || T.SqBiTNode[i] == -1) { // 越界或者为空结点
return true;
}
if (T.SqBiTNode[i] <= lower || T.SqBiTNode[i] >= upper) {
return false;
}
return helper(T, 2 * i + 1, lower, T.SqBiTNode[i]) && helper(T, 2 * i + 2, T.SqBiTNode[i], upper);
}
bool isValidBST(SqBiTree T) {
return helper(T, 0, LONG_MIN, LONG_MAX);
}
int main() {
int a1[10] = {40, 25, 60, -1, 30, -1, 80, -1, -1, 27};
SqBiTree bt1;
memset(bt1.SqBiTNode, 0, sizeof(bt1.SqBiTNode));
bt1.ElemNum = 10;
for (int i = 0; i < bt1.ElemNum; ++i) {
bt1.SqBiTNode[i] = a1[i];
}
int ans1 = isValidBST(bt1);
if (ans1 == true) {
printf("T1 is a binary search tree\n");
} else {
printf("T1 is not a binary search tree\n");
}
int a2[11] = {40, 50, 60, -1, 30, -1, -1, -1, -1, -1, 35};
SqBiTree bt2;
memset(bt2.SqBiTNode, 0, sizeof(bt2.SqBiTNode));
bt2.ElemNum = 11;
for (int i = 0; i < bt2.ElemNum; ++i) {
bt2.SqBiTNode[i] = a2[i];
}
int ans2 = isValidBST(bt2);
if (ans2 == true) {
printf("T2 is a binary search tree\n");
} else {
printf("T2 is not a binary search tree\n");
}
return 0;
}
复杂度分析
- 时间复杂度： 𝑂(𝑛) ，其中 𝑛 为二叉树的结点个数。在递归调用的时候二叉树的每个结点最多被访问一次，因此时间复杂度为 𝑂(𝑛) 。
- 空间复杂度： 𝑂(𝑛) ，其中 𝑛 为二叉树的结点个数。递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，即二叉树的高度。最坏情况下二叉树为一条链，树的高度为 𝑛 ，递归最深达到 𝑛 层，故最坏情况下空间复杂度为 𝑂(𝑛) 。
方法二：中序遍历
利用二叉搜索树的性质的推论：中序遍历为单调递增序列。
递归遍历：
考虑保存整个中序遍历序列，最后进行检查。
C代码如下（含测试用例）：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 20011
#define false 0
#define true 1
typedef int bool;
typedef struct { // MAX_SIZE为已定义常量
int SqBiTNode[MAX_SIZE]; // 保存二叉树结点值的数组
int ElemNum; // 实际占用的数组元素个数
}SqBiTree;
void inorder(SqBiTree T, int i, int *a, int *j) {
if (i >= T.ElemNum || T.SqBiTNode[i] == -1) { // 越界或者为空结点
return;
}
inorder(T, 2 * i + 1, a, j);
a[(*j)++] = T.SqBiTNode[i];
inorder(T, 2 * i + 2, a, j);
}
bool isValidBST(SqBiTree T){
int *a = (int *)malloc(sizeof(int) * MAX_SIZE);
int j = 0;
inorder(T, 0, a, &j);
for(int k = 0; k < j - 1; k++) {
if(a[k] >= a[k + 1]) {
return false;
}
}
return true;
}
int main() {
int a1[10] = {40, 25, 60, -1, 30, -1, 80, -1, -1, 27};
SqBiTree bt1;
memset(bt1.SqBiTNode, 0, sizeof(bt1.SqBiTNode));
bt1.ElemNum = 10;
for (int i = 0; i < bt1.ElemNum; ++i) {
bt1.SqBiTNode[i] = a1[i];
}
int ans1 = isValidBST(bt1);
if (ans1 == true) {
printf("T1 is a binary search tree\n");
} else {
printf("T1 is not a binary search tree\n");
}
int a2[11] = {40, 50, 60, -1, 30, -1, -1, -1, -1, -1, 35};
SqBiTree bt2;
memset(bt2.SqBiTNode, 0, sizeof(bt2.SqBiTNode));
bt2.ElemNum = 11;
for (int i = 0; i < bt2.ElemNum; ++i) {
bt2.SqBiTNode[i] = a2[i];
}
int ans2 = isValidBST(bt2);
if (ans2 == true) {
printf("T2 is a binary search tree\n");
} else {
printf("T2 is not a binary search tree\n");
}
return 0;
}
复杂度分析
- 时间复杂度： 𝑂(𝑛) ，其中 𝑛 为二叉树的结点个数。二叉树的每个结点最多被访问三次，因此时间复杂度为 𝑂(𝑛) 。
- 空间复杂度： 𝑂(𝑛) ，其中 𝑛 为二叉树的结点个数。递归栈最深为 𝑛 ，中序遍历数组大小为 𝑛 ，因此需要额外的 𝑂(𝑛) 的空间。
优化空间复杂度，使用一个变量 𝑝𝑟𝑒𝑣 记录前驱。由于非空二叉树T的结点值均为正数，初始化 𝑝𝑟𝑒𝑣=0 。
C代码如下（含测试用例）：
#include <stdio.h>
#include <string.h>
#define MAX_SIZE 20011
#define false 0
#define true 1
typedef int bool;
typedef struct { // MAX_SIZE为已定义常量
int SqBiTNode[MAX_SIZE]; // 保存二叉树结点值的数组
int ElemNum; // 实际占用的数组元素个数
}SqBiTree;
bool inorder(SqBiTree T, int i, int* prev) {
if (i >= T.ElemNum || T.SqBiTNode[i] == -1) { // 越界或者为空结点
return true;
}
if (!inorder(T, 2 * i + 1, prev)) {
return false;
}
if (prev > T.SqBiTNode[i]) {
return false;
}
prev = T.SqBiTNode[i];
return inorder(T, 2 * i + 2, prev);
}
bool isValidBST(SqBiTree T) {
int prev = 0;
return inorder(T, 0, prev);
}
int main() {
int a1[10] = {40, 25, 60, -1, 30, -1, 80, -1, -1, 27};
SqBiTree bt1;
memset(bt1.SqBiTNode, 0, sizeof(bt1.SqBiTNode));
bt1.ElemNum = 10;
for (int i = 0; i < bt1.ElemNum; ++i) {
bt1.SqBiTNode[i] = a1[i];
}
int ans1 = isValidBST(bt1);
if (ans1 == true) {
printf("T1 is a binary search tree\n");
} else {
printf("T1 is not a binary search tree\n");
}
int a2[11] = {40, 50, 60, -1, 30, -1, -1, -1, -1, -1, 35};
SqBiTree bt2;
memset(bt2.SqBiTNode, 0, sizeof(bt2.SqBiTNode));
bt2.ElemNum = 11;
for (int i = 0; i < bt2.ElemNum; ++i) {
bt2.SqBiTNode[i] = a2[i];
}
int ans2 = isValidBST(bt2);
if (ans2 == true) {
printf("T2 is a binary search tree\n");
} else {
printf("T2 is not a binary search tree\n");
}
return 0;
}
复杂度分析
- 时间复杂度： 𝑂(𝑛) ，其中 𝑛 为二叉树的结点个数。二叉树的每个结点最多被访问三次，因此时间复杂度为 𝑂(𝑛) 。
- 空间复杂度： 𝑂(𝑛) ，其中 𝑛 为二叉树的结点个数。递归栈最深为 𝑛 ，因此需要额外的 𝑂(𝑛) 的空间。
迭代遍历：
迭代遍历是对递归遍历的改进，如果中途检测到不符合二叉搜索树性质，可以直接终止，加速程序运行，但无法降低算法时间复杂度。
C代码如下（含测试用例）：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#define MAX_SIZE 20011
#define false 0
#define true 1
typedef int bool;
typedef struct { // MAX_SIZE为已定义常量
int SqBiTNode[MAX_SIZE]; // 保存二叉树结点值的数组
int ElemNum; // 实际占用的数组元素个数
}SqBiTree;
bool isValidBST(SqBiTree T) {
int *stk = (int *)malloc(sizeof(int) * MAX_SIZE);
int top = 0; // 栈顶指针
int prev = -1; // 初始前驱下标
int curr = 0; // 初始指向根结点
while (top > 0 || (curr < T.ElemNum && T.SqBiTNode[curr] != -1)) {
while (curr < T.ElemNum && T.SqBiTNode[curr] != -1) {
stk[top++] = curr;
curr = curr * 2 + 1;
}
curr = stk[--top];
// 如果中序遍历得到的结点的值小于前驱，说明不是二叉搜索树
if (T.SqBiTNode[curr] < (prev == -1 ? INT_MIN : T.SqBiTNode[prev])) {
return false;
}
prev = curr;
curr = curr * 2 + 2;
}
return true;
}
int main() {
int a1[10] = {40, 25, 60, -1, 30, -1, 80, -1, -1, 27};
SqBiTree bt1;
memset(bt1.SqBiTNode, 0, sizeof(bt1.SqBiTNode));
bt1.ElemNum = 10;
for (int i = 0; i < bt1.ElemNum; ++i) {
bt1.SqBiTNode[i] = a1[i];
}
int ans1 = isValidBST(bt1);
if (ans1 == true) {
printf("T1 is a binary search tree\n");
} else {
printf("T1 is not a binary search tree\n");
}
int a2[11] = {40, 50, 60, -1, 30, -1, -1, -1, -1, -1, 35};
SqBiTree bt2;
memset(bt2.SqBiTNode, 0, sizeof(bt2.SqBiTNode));
bt2.ElemNum = 11;
for (int i = 0; i < bt2.ElemNum; ++i) {
bt2.SqBiTNode[i] = a2[i];
}
int ans2 = isValidBST(bt2);
if (ans2 == true) {
printf("T2 is a binary search tree\n");
} else {
printf("T2 is not a binary search tree\n");
}
return 0;
}
复杂度分析
- 时间复杂度： 𝑂(𝑛) ，其中 𝑛 为二叉树的结点个数。二叉树的每个结点最多被访问三次，因此时间复杂度为 𝑂(𝑛) 。
- 空间复杂度： 𝑂(𝑛) ，其中 𝑛 为二叉树的结点个数。栈最多存储 𝑛 个结点，因此需要额外的 𝑂(𝑛) 的空间。
Morris遍历：
Morris遍历是对迭代遍历的进一步优化。
Morris是就是著名的计算机科学家J.H.Morris，他还与D.E.Knuth和V.R.Pratt一起提出了KMP算法。
Morris中序遍历伪代码如下：
PRINT-BINARY-TREE(T)
x = T.root
y = NIL // rightmost node in x's left subtree
while x ≠ NIL
y = x.left
if y ≠ NIL
while y.right ≠ NIL and y.right ≠ x
y = y.right
if y.right == NIL
y.right = x
x = x.left
continue
else y.right = NIL
print x.key
x = x.right
本质是构造出类似中序遍历线索二叉树的二叉树，构造线索指向后继（下图中用虚线表示）。但注意，若能通过二叉树的孩子指针找到后继的线索（例如二叉树T1中关键字25所在结点到关键字27所在结点的线索），则该线索无需构造，如下图所示：
二叉树静态数组的Morris遍历难度比指针结点表示的二叉树大，由于没有空指针和指针变换，考虑用空结点记录中序遍历后继指针指向。为了区分指针和数字，且避开缺省值-1，下标值从-2开始储存。因为这里所有元素为正，即 𝑥.𝑘𝑒𝑦≥1 ，我们要存储下标，因为树不为空，所以 𝑦.𝑟𝑖𝑔ℎ𝑡 的下标大于等于0，要避开所有正数和缺省-1，结构体SqBiTNode数组中没有填充的部分默认为0，也要完美避开，存负的下标值-2，这样就符合小于等于-2，正好没有产生任何冲突。
由于 𝑥 左子树的最右结点不可能右孩子，所以完全可以直接用空结点存储中序遍历后继结点下标，但是如果是需要记录会发生冲突的线索比如后序遍历的后继线索，这样做就会出现冲突，一旦出现冲突，就需要开辟 𝑂(𝑛) 的数组记录。用静态数组表示的二叉树的Morris遍历的空间复杂度为 𝑂(1) 不简单是巧合。
修改指针这部分是真的复杂，目前想到的办法通过正负号来区分里面存的是下标还是元素值，保证此算法是一个原地算法。这个思路可以参考2018年第41题，其最优解为原地哈希，都是运用负号进行标记，两者原地构造存储有异曲同工之妙。
这里默认MAX_SIZE足够大，不会造成记录后继指针指向时数组越界。
C代码如下（含测试用例）：
#include <stdio.h>
#include <string.h>
#define MAX_SIZE 20011
#define false 0
#define true 1
typedef int bool;
typedef struct { // MAX_SIZE为已定义常量
int SqBiTNode[MAX_SIZE]; // 保存二叉树结点值的数组
int ElemNum; // 实际占用的数组元素个数
}SqBiTree;
bool isValidBST(SqBiTree T) {
int prev = -1; // 前驱结点下标，初始化为NIL
int x = 0; // 初始指向根结点下标，初始化为根结点下标 x = T.root
int y = -1; // x 左子树的最右结点下标，初始化为NIL y = NIL
while (x < T.ElemNum && T.SqBiTNode[x] != -1) { // while x != NIL
y = 2 * x + 1; // y = x.left
if (y < T.ElemNum && T.SqBiTNode[y] != -1) { // if y != NIL
while (T.SqBiTNode[2 * y + 2] != -1 && T.SqBiTNode[2 * y + 2] != 0 && -T.SqBiTNode[2 * y + 2] - 2 != x) { // while (y.right != NIL && y.right != x)
y = T.SqBiTNode[2 * y + 2] < -1 ? -T.SqBiTNode[2 * y + 2] - 2 : 2 * y + 2; // y = y.right
}
if (T.SqBiTNode[2 * y + 2] == -1 || T.SqBiTNode[2 * y + 2] == 0) { // if (y.right == NIL)
T.SqBiTNode[2 * y + 2] = -(x + 2); // y.right = x
x = 2 * x + 1; // x = x.left
continue;
} else {
T.SqBiTNode[2 * y + 2] = -1; // y.right = NIL
}
}
if (T.SqBiTNode[x] < (prev == -1 ? -MAX_SIZE : T.SqBiTNode[prev])) { // 比较当前结点和前驱结点的值检查是否违反二叉搜索树性质
return false;
}
prev = x; // 更新前驱结点下标
x = T.SqBiTNode[2 * x + 2] < -1 ? -T.SqBiTNode[2 * x + 2] - 2 : 2 * x + 2; // x = x.right
}
return true;
}
int main(int argc, const char * argv[]) {
int a1[10] = {40, 25, 60, -1, 30, -1, 80, -1, -1, 27};
SqBiTree bt1;
memset(bt1.SqBiTNode, 0, sizeof(bt1.SqBiTNode));
bt1.ElemNum = 10;
for (int i = 0; i < bt1.ElemNum; ++i) {
bt1.SqBiTNode[i] = a1[i];
}
int ans1 = isValidBST(bt1);
if (ans1 == true) {
printf("T1 is a binary search tree\n");
} else {
printf("T1 is not a binary search tree\n");
}
int a2[11] = {40, 50, 60, -1, 30, -1, -1, -1, -1, -1, 35};
SqBiTree bt2;
memset(bt2.SqBiTNode, 0, sizeof(bt2.SqBiTNode));
bt2.ElemNum = 11;
for (int i = 0; i < bt2.ElemNum; ++i) {
bt2.SqBiTNode[i] = a2[i];
}
int ans2 = isValidBST(bt2);
if (ans2 == true) {
printf("T2 is a binary search tree\n");
} else {
printf("T2 is not a binary search tree\n");
}
return 0;
}
复杂度分析
- 时间复杂度： 𝑂(𝑛) ，其中 𝑛 为二叉树的结点个数。二叉树的每个结点最多被访问三次，因此时间复杂度为 𝑂(𝑛) 。
- 空间复杂度： 𝑂(1) ，中间过程额外需要常数个变量。
注：参考力扣98. 验证二叉搜索树。
2023¶
41题：已知有向图 𝐺 采用邻接矩阵存储，类型定义如下：
typedef struct { // 图的类型定义
int numVertices, numEdges; // 图中顶点数和有向边数
char VerticesList[MAXV]; // 顶点表，MAXV为已定义常量
int Edge[MAXV][MAXV]; // 邻接矩阵
}MGraph;
将图中出度大于入度的顶点称为 K 顶点。例如在题41图中，顶点 a 和 b 都是 K 顶点。
题41图
请设计算法： int printVertices(MGraph G)，对给定的任意非空有向图 G，输出 G 中所有 K 顶点，并返回 K 顶点的个数。要求：
⑴ 给出算法的基本设计思想。
⑵ 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
本题考察入度和出度的定义和计数法。
未找到题源。
题源判定：命题组原创
题目难度：⭐️
解答：
本题与2021年第41题及其相似，但是由于要分别统计入度和出度，比2021年第41题略难，2021年第41题408史上最简单算法题，本题为408史上第二简单算法题。
⑴ 由于 𝐺 是采用邻接矩阵 𝐺.𝐸𝑑𝑔𝑒 表示， 𝐺.𝐸𝑑𝑔𝑒[𝑖][𝑗]=1 表示存在有向边 (𝑖,𝑗) ， 𝐺.𝐸𝑑𝑔𝑒[𝑖][𝑗]=0 表示不存在有向边 (𝑖,𝑗) 。
算法的基本设计思想如下：
- 第一步：统计所有顶点的入度和出度。若存在边 (𝑖,𝑗) ，即 𝐺.𝐸𝑑𝑔𝑒[𝑖][𝑗]=1 ，则顶点 𝑖 的出度加一，顶点 𝑗 的入度加一。若不存在边 (𝑖,𝑗) ，即 𝐺.𝐸𝑑𝑔𝑒[𝑖][𝑗]=0 ，则顶点 𝑖 的出度不变，顶点 𝑗 的入度不变。综上，顶点 𝑖 的出度加 𝐺.𝐸𝑑𝑔𝑒[𝑖][𝑗] ，顶点 𝑗 的入度加 𝐺.𝐸𝑑𝑔𝑒[𝑖][𝑗] 。
- 第二步：统计所有顶点中出度大于入度的顶点（即 K 顶点）的个数，本题还需要打印 K 顶点，注意是打印 K 顶点的名称（char 类型），不是打印 K 顶点的下标（int 类型），所以需要通过 VerticesList 将顶点下标转换为顶点名称。
⑵ 根据上述思路，C代码如下（含测试用例）：
#include <stdio.h>
#include <string.h>
#define MAXV 11
typedef struct { // 图的类型定义
int numVertices, numEdges; // 图中顶点数和有向边数
char VerticesList[MAXV]; // 顶点表，MAXV为已定义常量
int Edge[MAXV][MAXV]; // 邻接矩阵
} MGraph;
int printVertices(MGraph G) {
int indegrees[G.numVertices];
int outdegrees[G.numVertices];
memset(indegrees, 0, sizeof(indegrees));
memset(outdegrees, 0, sizeof(outdegrees));
// 遍历无向图统计所有点的出度和入度
for (int i = 0; i < G.numVertices; i++) {
for (int j = 0; j < G.numVertices; j++) {
outdegrees[i] += G.Edge[i][j];
indegrees[j] += G.Edge[i][j];
}
}
int count = 0;
// 遍历indegrees和outdegrees数组统计出度大于入度的顶点
for (int i = 0; i < G.numVertices; i++) {
if (outdegrees[i] > indegrees[i]) {
printf("%c", G.VerticesList[i]);
count++;
}
}
return count;
}
int main() {
MGraph G;
G.numEdges = 5;
G.numVertices = 4;
memset(G.VerticesList, 0, sizeof(G.numVertices));
char V[4] = {'a', 'b', 'c', 'd'};
for (int i = 0; i < G.numVertices; i++) {
G.VerticesList[i] = V[i];
}
memset(G.Edge, 0, sizeof(G.numVertices));
int M[4][4] = {{0, 1, 0, 1}, {0, 0, 1, 1}, {0, 0, 0, 1}, {0, 0, 0, 0}};
for (int i = 0; i < G.numVertices; i++) {
for (int j = 0; j < G.numVertices; j++) {
G.Edge[i][j] = M[i][j];
}
}
int count = printVertices(G);
printf("%d", count);
return 0;
}
复杂度分析
- 时间复杂度： 𝑂(𝑛2) ，其中 𝑛 为图中点个数。因为需要遍历整个邻接矩阵，所以为 𝑂(𝑛2) 。
- 空间复杂度： 𝑂(𝑛) ，开辟了 𝑂(𝑛) 大小的辅助数组。
时间复杂度无法优化，我们考虑优化空间复杂度，去掉辅助数组，边遍历边统计。修改后C代码如下（含测试用例）：
#include <stdio.h>
#include <string.h>
#define MAXV 11
typedef struct { // 图的类型定义
int numVertices, numEdges; // 图中顶点数和有向边数
char VerticesList[MAXV]; // 顶点表，MAXV为已定义常量
int Edge[MAXV][MAXV]; // 邻接矩阵
} MGraph;
int printVertices(MGraph G) {
int count = 0, indegree = 0, outdegree = 0;
// 遍历无向图统计所有点的出度和入度
for (int i = 0; i < G.numVertices; i++) {
indegree = 0; // i的入度
outdegree = 0; // i的出度
for (int j = 0; j < G.numVertices; j++) {
outdegree += G.Edge[i][j];
indegree += G.Edge[j][i];
}
if (outdegree > indegree) {
printf("%c", G.VerticesList[i]);
count++;
}
}
return count;
}
int main() {
MGraph G;
G.numEdges = 5;
G.numVertices = 4;
memset(G.VerticesList, 0, sizeof(G.numVertices));
char V[4] = {'a', 'b', 'c', 'd'};
for (int i = 0; i < G.numVertices; i++) {
G.VerticesList[i] = V[i];
}
memset(G.Edge, 0, sizeof(G.numVertices));
int M[4][4] = {{0, 1, 0, 1}, {0, 0, 1, 1}, {0, 0, 0, 1}, {0, 0, 0, 0}};
for (int i = 0; i < G.numVertices; i++) {
for (int j = 0; j < G.numVertices; j++) {
G.Edge[i][j] = M[i][j];
}
}
int count = printVertices(G);
printf("%d", count);
return 0;
}
复杂度分析
- 时间复杂度： 𝑂(𝑛2) ，其中 𝑛 为图中点个数。因为需要遍历整个邻接矩阵，所以为 𝑂(𝑛2) 。
- 空间复杂度： 𝑂(1) ，使用了常数个辅助变量。
2024¶
41题
本题考察入度的定义和计数法以及其在拓扑排序中的应用。
未找到题源。
题源判定：命题组原创
题目难度：⭐️⭐️⭐️
题源分布¶
LeetCode：2009、2010、2012、2018、2019、2020和2022，共计7次，选用题目主要集中在前200道经典题目，难度简单或中等，少部分出现在前800题，难度为困难。
程序员面试金典：2013和2015，共计2次，与LeetCode高度相似，都是经典题目，选用题目难度简单或中等。
PAT：2017和2021，共计2次，选用题目全部来自PAT甲级，难度简单或中等。
算法导论：2011，共计1次，选用题目难度困难。
命题组原创：2014、2016、2023和2024，共计4次，原创题目基本紧扣《数据结构（C语言版）》中数据结构的定义，难度简单或中等。