问题描述:给定的n个整数,计算其中最小的K个数。
最直观的解法莫过于将n个数按升序排列后输出前k个。但是就效率来看,这种方法并不是最理想的。一种改进方法是借助快速排序中对数组的划分,以第k个元素对数组进行划分,使得比第k个数字小的数字都在其左边,比其大的数字都在它的右边。
void Swap(int &a, int &b) { int c = a; a = b; b = c; } int Partition(int data[], int length, int start, int end) { if(data == NULL || length <= 0) return -1; int index = start - 1; for(int i = start; i < end; ++i) { if(data[i] < data[end]) { ++index; swap(data[i], data[index]); } } ++index; Swap(data[index], data[end]); return index; } void GetKLeastNumbers(int data[], int length, int result[], int k) { if(data == NULL || length <= 0 || result == NULL || k <= 0) return; int start = 0, end = length - 1; int index = Partition(data, length, start, end); while(index != k - 1) // 第k个数作为数组划分依据 { if(index > k - 1) index = Partition(data, length, start, index - 1); else index = Partition(data, length, index + 1, end); } for(int i = 0; i < k; ++i) result[i] = data[i]; }
通过分析可以确定算法的时间复杂度是O(n),是一种比较高效的解法。但是上述算法存在的问题是修改了原始数组数据,因此在不允许修改原始数据的情况下的应用就会受到限制。
在不修改原始数据的前提条件下,我们可以创建一个大小为k的容器存放最小的k个数。再对n个整数进行遍历,如果容器中的数少于k个,则直接把读入的数存入容器;如果容器中的数大于等于k个,同时当前读入的数小于容器中最大的数,那么删除容器中最大的数,将该数读入容器,否则不做操作。为了确保快速删除容器中最大的数,容器数据的存储可以考虑使用最大堆。由于最大堆的根结点的值大于它的子树中任意结点的值,因此可以在O(1)得到已有k个数中的最大者,删除和插入操作的时间则为O(lgk)。对n个数重复最大堆的插入、删除操作总的算法时间复杂度为O(nlgk)。下面是使用STL
multiset完成上述算法的实现代码。
//建立最大堆保存最小的k个数 void GetKLeastNumbers(const int data[], int length, multiset<int, greater<int> > &result, int k) { if(data == NULL || k < 1 || k > length) // 数据合法性判断 return; result.clear(); multiset<int, greater<int> >::iterator iter; for(int i = 0; i < length; ++i) { if(result.size() < k) result.insert(data[i]); else { iter = result.begin(); if(*iter < *(result.begin())) { result.erase(iter); result.insert(data[i]); } } } }
上述两种方法都实现求最小k个数,虽然第二种方法比第一种方法慢一些,但是它并不修改原始数据,另外比较适用于海量数据处理的情形。因此两种方法各有优劣,实际应用时视具体情况确定算法的选用。