【数据结构】【面试题】找N个数据中最大的K个数据
如果不限定条件的话,这个问题还是很好解决的,但是当我们要求时间复杂度为O(N),空间复杂度为O(1)时,问题就没那么好解决了。
创新互联建站是一家专注于成都网站设计、网站建设与策划设计,东胜网站建设哪家好?创新互联建站做网站,专注于网站建设十载,网设计领域的专业建站公司;建站业务涵盖:东胜等地区。东胜做网站价格咨询:028-86922220
简单的思路就是,创建一个大小为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; } } }
网页标题:【数据结构】【面试题】找N个数据中最大的K个数据
文章URL:http://scyanting.com/article/ijdess.html