24
- 首先给出单链表结点的数据类型定义：
typedef struct LNode{ int data; struct LNode* link; }LNode, *LinkList; 复制代码
- 一眼桶排，之前做过很多次这样的题，其实就是用一个辅助数组记录出现过的结点值
- 其实就是把出现的结点值看作数组下标，如果需要记录次数则数组元素代表出现次数
- 第一个数为21，则令辅助数组
arr[21]=1即可 - 因为
|data| <= n，只需要保存绝对值，所以申请一个大小为 n+1 的辅助数组就可以了 - 我们可以一边遍历，一边判断结点元素值的绝对值是否是第一次出现，不是则删除该结点
- 典型的拿空间换时间，时间复杂度O(m)，空间复杂度O(n)
void delSameAbsoluteValue(LinkList L, int n) { // 1.初始化辅助数组 int arr[n+1] = {0}; LNode *p = L, *del; // 2.遍历同时判别 while (p->link != NULL) { int m = abs(p->link->data); // 获得绝对值 if (arr[m] == 0) { arr[m] = 1; // 首次出现 p = p->link; } else { del = p->link; // 非首次出现直接删除 p->link = del->link; free(del); } } 复制代码
- 有一点需要说明一下
- 408考试的时候，好像是不允许
int arr[n+1] = {0}这种语法的 - 所以我们需要用
malloc()来创建数组，然后使用循环或者memset()将数组元素初始值置为0 - 注意
memset()只能将int数组初始化为0或-1
int arr[n+1] = {0}; // 推荐方法 int *arr = (int *)malloc(sizeof(int) * (n+1)); for (int i = 0; i < n+1; i++) { *(arr+i) = 0; } int *arr = (int *)malloc(sizeof(int) * (n+1)); memset(arr, 0, sizeof(int) * (n+1)); int arr[n+1]; memset(arr, 0, sizeof(arr));
