如果直接调用 sort API 然后要几个打印几个就没意思了,应该是和某个排序的内部过程结合
首先排除O(N2)的低效率排序算法,最先想到的其实是堆排序,小根堆,但是需要额外的空间
其次像快排、归并这样的也不合适……
我想到了可以这样,快排第一轮划分之后,将部分舍去……
应该就是这样了,堆排序或者快排
思路
4,5,1,6,2,7,3,8
快排
首先选择 4 作为第一个基准,大的放右边,小的放左边,最后我们可以得到 4 在整个排序序列中的索引位置,它是第 4 小的数字,正好满足目标,于是舍去右边一边,对剩下的继续进行快排
那么如果没这么巧合,要求的大于或者小于目标怎么办?
比如 k = 3,
快排是原地排序算法,但是题目要求返回一个数组
第一次 AC 代码
vector<int> getLeastNumbers(vector<int>& arr, int k) {
int len = arr.size();
if (len == 0)return {};
QuickSort(arr, 0, len - 1, k);
vector<int> res(k);// 准备长度为k的数组用于返回
copy(arr.begin(), arr.begin() + k, res.begin());
return res;
}
void QuickSort(vector<int>& arr, int start, int end, int k) {
int index = Paritition(arr, start, end);
// 如果index>k,那么大于index那一部分就不需要再处理了
// 所以只需要排index<=k的部分
if (start < index) QuickSort(arr, start, index - 1, k);
if (index < (k - 1) && index < end)QuickSort(arr, index + 1, end, k);
}
int RandomInRange(int start, int end) {
srand(time(nullptr));
return rand() % (end - start + 1) + start;
}
// 划分函数会返回每一次划分得到的基准的索引
int Paritition(vector<int>& arr, int start, int end) {
int index = RandomInRange(start, end);
swap(arr[index], arr[end]);// 既然基准是随便选的,这里能不能就直接选arr[end],这样还不用交换了
int small = start - 1;// small指向最后一个比基准小的元素,所以对于比基准大的元素small指针不会移动
// 服用index,因为之前index代表的索引没有意义,对应的数字我们也知道就是arr[end]
for (index = start; index < end; ++index) {
if (arr[index] < arr[end]) {
++small;
if (small != index) swap(arr[small], arr[index]);// 这里其实可以不判断直接换
}
}
// 等上面的循环结束,small指向最后一个比基准小的元素,基准在最后,中间的都是比基准大的元素
// 现在需要把基准放到它应该在的位置,最后做一次上面的交换动作,把基准插到small的最后去,更新small后,small指向的位置就是基准
++small;
swap(arr[small], arr[end]);
return small;
}
C++ 中有没有将一个数组的一部分,比如前 4 个数组提取或者转移到另一个数组中的函数呢?可以使用copy
函数
class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
QuickSort(arr, 0, arr.size() - 1, k);
return vector<int>(arr.begin(), arr.begin() + k);
}
void QuickSort(vector<int>& arr, int start, int end, int k) {
int index = Paritition(arr, start, end);
if (start < index) QuickSort(arr, start, index - 1, k);
if (index < (k - 1) && index < end)QuickSort(arr, index + 1, end, k);
}
int RandomInRange(int start, int end) {
srand(time(nullptr));
return rand() % (end - start + 1) + start;
}
int Paritition(vector<int>& arr, int start, int end) {
int index = RandomInRange(start, end);
swap(arr[index], arr[end]);
int small = start - 1;
for (index = start; index < end; ++index) {
if (arr[index] < arr[end]) {
++small;
if (small != index) swap(arr[small], arr[index]);
}
}
++small;
swap(arr[small], arr[end]);
return small;
}
};
感觉时间复杂度并没有好到哪儿去,这个剪枝意义不大,还不如直接 sort
vector<int> getLeastNumbers(vector<int>& arr, int k) {
sort(arr.begin(), arr.end());
return vector<int>(arr.begin(), arr.begin() + k);
}
另外我注意到的为什么每次选择随机数然后与末尾交换,直接选择末尾元素作为基准不是更省事的问题,选择随机数可以在某种程度上避免性能下降的情况,例如输入数组已经基本有序的情况下,快速排序的分割不均匀,导致递归深度增加
标签:index,arr,end,Offer,int,个数,40,start,small From: https://www.cnblogs.com/yaocy/p/17637912.html