输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
第一个思路：利用大根堆。也是解决top k海量数据的关键
延伸部分(重要)
大堆还是小堆的选择很重要，不是寻找最小的k个元素就要选择小堆，而且恰恰相反。
寻找最小的k个数，其实就是寻找第k个大的元素，即寻找k个数中最大的，
不断调整堆，堆得元素个数是k，堆顶是最大值，遍历完初始数组后，
堆中存在的元素即使我们所要寻找的k个最小元素。
题解：
1：首先选取前K个数建立最大堆（根结点值大于左右结点值）。
2：此后，每次从原数组中取一个元素与根进行比较，如果大于根结点的元素，忽视之，取下一个数组元素继续该过程；
如果小于根结点的元素，则将其加入最大堆，并进行堆调整(和堆顶替换)，将根元素移动到最后再删除，
即保证最大堆中的元素仍然是排名前K的数，且根元素仍然最大。
make_heap函数用法
这里使用了make_heap构建堆也可以手动实现堆
/* 先后建一个大根堆，利用make_heap函数， 然后将容器剩余元素比较， * 小于堆顶的就调整,(入堆，堆顶元素在弹出), * 大于堆顶的跳过 * 最后对容器排序 */ class Solution { public: vector<int> GetLeastNumbers_Solution(vector<int> input, int k) { vector<int> vec; int len =input.size(); if (len <= 0 || len < k || k <= 0 ) return vec; // 将k个数放入vec，然后构建成大根堆 for (int i = 0; i < k; i++) vec.push_back(input[i]); make_heap(vec.begin(), vec.end(), less<int>()); for(int i = k; i < len; i++) { if (input[i] > vec.front()) // 当前元素大于大根堆堆顶，跳过 continue; else { vec.push_back(input[i]); // 添加新元素，调整堆 push_heap(vec.begin(), vec.end()); // 将堆顶元素调整到最后 pop_heap(vec.begin(), vec.end()); // 将最大的放到最后，然后对容器最后一个删除 vec.pop_back(); //删除最后那个元素 } } // 上面是将最小的k个放入了vec容器中，但是是乱序的,但是这个题也可以不用排序 sort_heap(vec.begin(),vec.end()); return vec; } };
这里是手动实现堆的， 面试常考手写堆排和快排哦
class Solution2 { public: // 首先构建一个大根堆(len 是数组长度，index是第一个非叶子节点下标) 构建长度为len，从index开始 void adjust(vector<int>&vec, int len, int index) { if (index > len) // 递归出口 return ; int left = 2*index + 1; // index的左孩子 int right = 2*index + 2; // index的右孩子 int maxIdx = index; // 将maxidx作为子树的最大值, 在下标不越界的情况下 if (vec[maxIdx] < vec[left] && left < len) { maxIdx = left; } if(vec[maxIdx] < vec[right] && right < len) { maxIdx = right; } if (index != maxIdx) // 最大值不是在堆顶就交换 { swap(vec[index], vec[maxIdx]); adjust(vec, len, maxIdx); // 递归所有的子树，构建 } } vector<int> GetLeastNumbers_Solution(vector<int> input, int k) { int len = input.size(); if (len <= 0 || len < k || k <= 0 ) return vector<int>(); vector<int>max_heap; for(int i = 0; i < k; i++) max_heap.push_back(input[i]); // 对k个元素进行构建 小根堆， 循环结束后得到的是一个含有k个元素的大根堆 for(int i = k/2-1; i >= 0; i--) adjust(max_heap, k, i); // 对input容器中的剩余元素和堆顶比较 for(int i = k; i < len; i++) { if (input[i] < max_heap[0]) { max_heap[0] = input[i]; adjust(max_heap, k, 0); // 对堆顶元素进行调整 } } return max_heap; } };
第二个思路就是先进性排序，然后输出，但是这并不是出题者要考察的，
但是我们也给出代码(手写快排）加深印象
// // Created by LK on 2020/3/15. // /* * 输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。 */ #include <iostream> #include <vector> using namespace std; // 思路一排序 class Solution { public: void quick_sort(vector<int>&arr, int left, int right) { int i = left; int j = right; int temp; if (left < right) { temp = arr[left]; while(i < j) { // 从后向前找个小的 while(i < j&& arr[j] >= temp) --j; if (i < j) arr[i++] = arr[j]; // 从前往后找个大的 while (i <j && temp > arr[i]) ++i; if (i < j) arr[j--] = arr[i]; } arr[i] = temp; quick_sort(arr, left, i-1); quick_sort(arr, i+1, right); } } vector<int> GetLeastNumbers_Solution(vector<int> input, int k) { vector<int> result; int len = input.size(); if (k <= 0 || k > len) return result; quick_sort(input, 0, input.size()-1); for(int i = 0; i < k; i++) result.push_back(input[i]); return result; } }; int main() { vector<int> input = {4,5,1,6,2,7,3,8}; int k = 4; Solution s; input = s.GetLeastNumbers_Solution(input, k); for(int i = 0; i < k; i++) cout << input[i]<<" "; return 0; }