当前位置: 首页 > news >正文

C语言 | Leetcode C语言题解之第480题滑动窗口中位数

题目:

题解:

struct Heap {int* heap;int heapSize;int realSize;bool (*cmp)(int, int);
};void init(struct Heap* obj, int n, bool (*cmp)(int, int)) {obj->heap = malloc(sizeof(int) * (n + 1));obj->heapSize = 0;obj->cmp = cmp;
}bool cmp1(int a, int b) {return a < b;
}bool cmp2(int a, int b) {return a > b;
}void swap(int* a, int* b) {int tmp = *a;*a = *b, *b = tmp;
}void push(struct Heap* obj, int x) {int p = ++(obj->heapSize), q = p >> 1;obj->heap[p] = x;while (q) {if (!obj->cmp(obj->heap[q], obj->heap[p])) {break;}swap(&(obj->heap[q]), &(obj->heap[p]));p = q, q = p >> 1;}
}void pop(struct Heap* obj) {swap(&(obj->heap[1]), &(obj->heap[(obj->heapSize)--]));int p = 1, q = p << 1;while (q <= obj->heapSize) {if (q + 1 <= obj->heapSize) {if (obj->cmp(obj->heap[q], obj->heap[q + 1])) {q++;}}if (!obj->cmp(obj->heap[p], obj->heap[q])) {break;}swap(&(obj->heap[q]), &(obj->heap[p]));p = q, q = p << 1;}
}int top(struct Heap* obj) {return obj->heap[1];
}bool empty(struct Heap* obj) {return obj->heapSize == 0;
}struct HashTable {int key;int val;UT_hash_handle hh;
} * hashtable;void prune(struct Heap* obj) {while (!empty(obj)) {int num = top(obj);struct HashTable* tmp;HASH_FIND_INT(hashtable, &num, tmp);if (tmp == NULL) {break;}tmp->val--;if (!(tmp->val)) {HASH_DEL(hashtable, tmp);free(tmp);}pop(obj);}
}void makeBalance(struct Heap* small, struct Heap* large) {if (small->realSize > large->realSize + 1) {push(large, top(small));pop(small);--(small->realSize);++(large->realSize);prune(small);} else if (small->realSize < large->realSize) {push(small, top(large));pop(large);++(small->realSize);--(large->realSize);prune(large);}
}void insert(struct Heap* small, struct Heap* large, int num) {if (empty(small) || num <= top(small)) {push(small, num);++(small->realSize);} else {push(large, num);++(large->realSize);}makeBalance(small, large);
}void erase(struct Heap* small, struct Heap* large, int num) {struct HashTable* tmp;HASH_FIND_INT(hashtable, &num, tmp);if (tmp == NULL) {tmp = malloc(sizeof(struct HashTable));tmp->key = num;tmp->val = 1;HASH_ADD_INT(hashtable, key, tmp);} else {tmp->val++;}if (num <= top(small)) {--(small->realSize);if (num == top(small)) {prune(small);}} else {--(large->realSize);if (num == top(large)) {prune(large);}}makeBalance(small, large);
}double getMedian(struct Heap* small, struct Heap* large, int k) {return (k & 1) ? top(small) : (((double)top(small) + top(large)) / 2);
}double* medianSlidingWindow(int* nums, int numsSize, int k, int* returnSize) {hashtable = NULL;struct Heap* small = malloc(sizeof(struct Heap));init(small, numsSize, cmp1);struct Heap* large = malloc(sizeof(struct Heap));init(large, numsSize, cmp2);for (int i = 0; i < k; ++i) {insert(small, large, nums[i]);}double* ans = malloc(sizeof(double) * (numsSize - k + 1));*returnSize = 0;ans[(*returnSize)++] = getMedian(small, large, k);for (int i = k; i < numsSize; ++i) {insert(small, large, nums[i]);erase(small, large, nums[i - k]);ans[(*returnSize)++] = getMedian(small, large, k);}return ans;
}
http://www.lryc.cn/news/462499.html

相关文章:

  • LabVIEW开发如何实现降维打击
  • docker 文件目录迁移
  • Markdown 标题
  • 【动手学电机驱动】TI InstaSPIN-FOC(5)Lab04 力矩控制
  • Mysql的CommunicationsException
  • C++学习笔记----9、发现继承的技巧(二)---- 重用目的的继承
  • 锐评 Nodejs 设计模式 - 创建与结构型
  • 【RoadRunner】自动驾驶模拟3D场景构建 | 软件简介与视角控制
  • 15分钟学Go 第4天:Go的基本语法
  • 【Qt】Qt的介绍——Qt的概念、使用Qt Creator新建项目、运行Qt项目、纯代码方式、可视化操作、认识对象模型(对象树)
  • 论文笔记:PTR: Prompt Tuning with Rules for Text Classification
  • 服务器和中转机协同工作以提高网络安全
  • Java利用itextpdf实现pdf文件生成
  • 2010年国赛高教杯数学建模C题输油管的布置解题全过程文档及程序
  • datawhale大模型bot应用开发--task3:工作流
  • 期货配资系统风控逻辑开发/完整源代码
  • 汽车免拆诊断案例 | 2023款零跑C01纯电车后备厢盖无法电动打开和关闭
  • 分布式存储架构 与分布式一致性协议
  • Unity Apple Vision Pro 保姆级开发教程 - Simulator 模拟器使用
  • Vue 之 插件与组件的区别
  • 了解 ChatGPT 中的公平性问题
  • 【PHP】安装swoole时报错:No package ‘libbrotlienc‘ found
  • postgresql执行计划解读案例
  • Matlab实现粒子群优化算法优化随机森林算法模型 (PSO-RF)(附源码)
  • 使用 EasyExcel 相邻数据相同时行和列的合并,包括动态表头、数据
  • 985研一学习日记 - 2024.10.16
  • 安装mysql 5.5.62
  • AnaTraf | 网络性能监控系统的价值
  • 决策树和集成学习的概念以及部分推导
  • servlet基础与环境搭建(idea版)