新网创想网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
如果不限定条件的话,这个问题还是很好解决的,但是当我们要求时间复杂度为O(N),空间复杂度为O(1)时,问题就没那么好解决了。
成都创新互联公司-专业网站定制、快速模板网站建设、高性价比颍上网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式颍上网站制作公司更省心,省钱,快速模板网站建设找我们,业务覆盖颍上地区。费用合理售后完善,10年实体公司更值得信赖。简单的思路就是,创建一个大小为K=100的小堆,调整好,然后从K开始拿十万个数据一个一个跟堆头比较,如果比堆头大,就入堆,然后调整成最小堆,一直循环到第N=100000个数据。
void AdjustDown(int* _a, size_t size,int i) { int parent = i; int child = 2 * parent + 1; while (child < size) { //找出孩子中的最小值 if (child + 1 < size && _a[child + 1] < _a[child]) { ++child; } //与父节点做比较 if (_a[parent] > _a[child]) { swap(_a[parent], _a[child]); parent = child; child = parent * 2 + 1; } else { break; } } } //找N个数据中的大K个 int* GetKTop(int* a,size_t size,size_t n) { int* _a = new int[size]; for (int i = 0; i < size; i++) { _a[i] = a[i]; } //建堆 for (int i = (size - 2) / 2; i >= 0; i--) { AdjustDown(_a, size,i); } for (int i = 0; i < n - size; i++) { if (_a[0] < a[size + i]) { _a[0] = a[size + i]; AdjustDown(_a, size, 0); } } return _a; } void _AdjustDown(int* a, size_t size, int i) { int parent = i; int child = 2 * parent + 1; while (child < size) { //找出孩子中的大值 if (child + 1 < size && a[child] < a[child + 1]) { ++child; } //拿父节点与大子节点做比较 if (a[parent] < a[child]) { swap(a[parent], a[child]); parent = child; child = 2 * parent + 1; } else { break; } } }
创新互联www.cdcxhl.cn,专业提供香港、美国云服务器,动态BGP最优骨干路由自动选择,持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证, 机房独有T级流量清洗系统配攻击溯源,准确进行流量调度,确保服务器高可用性。佳节活动现已开启,新人活动云服务器买多久送多久。