题目描述
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,
/*
//暴力法：sort, O(nlogn)
//方法一：使用自带的stl函数
#include <algorithm>
using namespace std;
class Solution
{
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k)
{
if(k<=0 || k > input.size()) return vector<int>(); //处理非法输入
nth_element(input.begin(), input.begin()+k-1, input.end());
vector<int> result(input.begin(),input.begin()+k); //构造结果向量
return result;
}
};*/
/*
/*掌握
方法一：基于partition函数(快排中有用到，stl中也有，但是还是自己实现较好)
多次partition直到枢轴位置为k即可
缺点：会改变输入数组的元素位置
平均O(n)，每次partition 平均O(n),次数未知，真的是O(n)吗，存疑？
思考：最好情况为O(n),最坏情况为O(n^2)（如对于倒序排列的数组）
通过优化partition，比如三数中值枢轴法或随机初始化枢轴法，可以改善时间复杂度
分析参考：
考虑最坏情况下，每次 partition 将数组分为长度为 N-1 和 1 的两部分，然后在长的一边继续寻找第 K 大，此时时间复杂度为 O(N^2 )。
不过如果在开始之前将数组进行随机打乱，那么可以尽量避免最坏情况的出现。
而在最好情况下，每次将数组均分为长度相同的两半，运行时间 T(N) = N + T(N/2)，时间复杂度是 O(N)。
*/
#include <cstdlib>
class Solution
{
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k)
{
if(input.empty() || k<=0 || k > input.size()) return vector<int>(); //处理异常输入
int left = 0, right = input.size()-1;
int pivot_pos;
while(left <= right)//类似二分查找法
{
pivot_pos = partition(input, left, right);//如果要求最大的第k个数，可以对partition函数进行改造
if(pivot_pos < k-1)
left = pivot_pos + 1;
else if(pivot_pos > k-1)
right = pivot_pos - 1;
else
break;//此题要求的是返回最小的前k个数，如果仅返回最小的第k个数，直接在这里return a[pivot_pos]即可
vector<int> result(input.begin(), input.begin()+k); //构造结果向量
return result;
}
private:
int partition(vector<int>& a, int left, int right)
{
//随机初始化枢轴 5ms
//srand(time(nullptr)); //以当前时间为随机生成器的种子
//int pivotpos = rand()%(right - left + 1) + left; //产生【left,right】之间的数
//swap(a[pivotpos], a[left]); //将枢轴暂时放入起始位置
int pivot = left; //枢轴位置 4ms
while(left<right)
{
while(left < right && a[right] >= a[pivot]) right--; //找到本次扫描中第一个不满足枢轴规律的高位数
while(left < right && a[left] <= a[pivot]) left++; //找到本次扫描中第一个不满足枢轴规律的低位数
swap(a[left], a[right]); //交换以使满足枢轴规律
}//最后结果是left和right均指向枢轴位置
swap(a[left], a[pivot]); //将枢轴移动到位
return left; //返回枢轴位置
}
//
/*掌握
方法二：使用堆或者红黑树（平衡二叉搜索树）
用容器存储k个数，遍历输入向量过程中不断更新容器内的数（如果当前数小于容器中的最大值，则插入该数，删除原最大数）
优点：不需要修改输入数组，且适用于处理海量输入数据
O(nlogk)
*/
class Solution
{
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k)
{
if(input.empty() || k<=0 || k > input.size()) return vector<int>(); //处理异常输入
//仿函数中的greater<T>模板，从大到小排序(默认从小到大，左结点<父结点<根结点)
multiset<int,greater<int>> leastNums; //用红黑树存储这k个数
for(int ai:input)
{
if(leastNums.size() < k) leastNums.insert(ai); //将前k个元素插入容器
else
{
//第一个数为最大数
multiset<int, greater<int>>::iterator greatest_it = leastNums.begin();
//如果后续元素小于第一个元素，删除第一个，加入当前元素
if(ai < *greatest_it)
{
leastNums.erase(greatest_it);//删除原最大值
leastNums.insert(ai); //插入新元素(logk复杂度)
}
}
}
return vector<int>(leastNums.begin(), leastNums.end()); //返回结果向量(前k个最小的数)
}
};
暴力法：直接sort,O(nlogn)，leetcode用时12ms
/*掌握
方法一：基于partition函数(快排中有用到，stl中也有，但是还是自己实现较好)
多次partition直到枢轴位置为k即可
缺点：会改变输入数组的元素位置
leetcode 耗时4ms,若用pivot = left的做法，则耗时20ms
平均O(n)，O(1)
每次partition 平均O(n),次数未知，真的是O(n)吗，存疑？
思考：最好情况为O(n),最坏情况为O(n^2)（如对于倒序排列的数组）
通过优化partition，比如三数中值枢轴法或随机初始化枢轴法，可以改善时间复杂度
*/
class Solution
{
public:
int findKthLargest(vector<int>& a, int k)
{
if(a.empty() || k<=0 || k > a.size()) return 0; //处理异常输入
int left = 0, right = a.size()-1;
int pivot_pos;
while(left <= right)//类似二分查找法
{
pivot_pos = partition(a, left, right);//如果要求最大的第k个数，可以对partition函数进行改造
if(pivot_pos < k-1)
left = pivot_pos + 1;
else if(pivot_pos > k-1)
right = pivot_pos - 1;
else
return a[pivot_pos];
}
}
private:
int partition(vector<int>& a, int left, int right)
{
srand(time(nullptr)); //以当前时间为随机生成器的种子
int pivotpos = rand()%(right - left + 1) + left; //产生【left,right】之间的数
swap(a[pivotpos], a[left]); //将枢轴暂时放入起始位置
int pivot = left; //枢轴位置
while(left<right)
{
//改造为从大到小partition,注意符号的变化
while(left < right && a[right] <= a[pivot]) right--; //找到本次扫描中第一个不满足枢轴规律的高位数
while(left < right && a[left] >= a[pivot]) left++; //找到本次扫描中第一个不满足枢轴规律的低位数
swap(a[left], a[right]); //交换以使满足枢轴规律
}//最后结果是left和right均指向枢轴位置
swap(a[left], a[pivot]); //将枢轴移动到位
return left; //返回枢轴位置
}
};
方法二：维护一个堆或者平衡二叉查找树存储这k个数
/*掌握
改进：维护一个大小为k的小顶堆，扫描输入数据，不断更新小顶堆的内容
最后堆顶元素即可n个数中第k大的数
leetcode耗时4ms
每次堆调整平均时间复杂度为O(logk)，共n次调整，故时间复杂度为O(nlogk)
O(nlogk), O(k)
*/
#include <algorithm>
#inlude <queue>
class Solution
{
public:
int findKthLargest(vector<int>& a, int k)
{
if(a.empty() || k<=0 || k>a.size()) return 0;//处理非法输入（可依题目返回适当值）
priority_queue<int,vector<int>,greater<int>> minheap; //构建小顶堆
for(int i = 0; i < a.size();i++)
{
if(i <= k-1)
minheap.push(a[i]); //将前k个元素插入容器
else
{
if(a[i] > minheap.top()) //如果当前元素大于容器中最小的元素，则将该元素push进容器
{
minheap.pop();
minheap.push(a[i]);//每次堆调整复杂度为O（logk）
}
}
}
return minheap.top();//返回堆顶元素,即为n个数中第k大的数（如果要返回前k个数，需将最后的minheap全部pop）
}
/*了解
用stl中make_heap函数，构建大顶堆，然后逐次输出堆顶元素(原理与用priority_queue相同，不过没有额外空间)
用时11ms
*/
#include <algorithm>
class Solution
{
public:
int findKthLargest(vector<int>& nums, int k)
{
make_heap(nums.begin(),nums.end());//构建大顶堆，用nums存储，与下面区别就是节省了空间
for(int i = 0; i<k-1;i++)
{
pop_heap(nums.begin(),nums.end()); //将堆顶元素移至末尾，重新调整使（begin~end-1）的元素满足堆规律
nums.pop_back(); //移除末尾元素
}
return nums[0];
}
//用stl中sort函数，用时12ms
/*
#include <algorithm>
class Solution
{
public:
int findKthLargest(vector<int>& nums, int k)
{
sort(nums.rbegin(), nums.rend()); //nums.rbegin()返回指向容器最后元素的逆向迭代器（因为sort默认按从小到大排序），
//sort将rbegin()指向位置当做第一个元素，故可以实现从大到小排序
return nums[k-1]; //第k个数，注意这里索引为k-1
}
};
*/
/*
//用stl中nth_element函数。?为什么没有sort()或者堆排序快
//用时14ms
#include <algorithm>
class Solution
{
public:
int findKthLargest(vector<int>& nums, int k)
{
//nth_element(nums.begin(), nums.begin()+k-1, nums.end(),customMore);
nth_element(nums.begin(), nums.begin()+k-1, nums.end(),greater<int>()); //原理为快排
//这里直接用STL里的函数，比较函数设置为greater(默认为小数在前)，注意中间(k-1)表示第k个最大的数
return nums[k-1]; //第k个数，注意这里索引为k-1
}
};
*/
/*
// 用自定义函数对象排序
struct
{
bool operator()(int a, int b) const
{
return a > b;
}
}customMore;
*/
