class Solution { public: vector<int> getLeastNumbers(vector<int>& arr, int k) { vector<int> result; int t = 0; for (int i = 0; i < k; i++) { for (int j = i+1; j < arr.size(); j++) { if (arr[i] > arr[j]) { t = arr[i]; arr[i] = arr[j]; arr[j] = t; } } result.push_back(arr[i]); } return result; } };
class Solution { public: vector<int> getLeastNumbers(vector<int>& arr, int k) { sort(arr.begin(), arr.end()); return vector(arr.begin(), arr.begin()+k); } };
class Solution { public: vector<int> getLeastNumbers(vector<int>& arr, int k) { vector <int> result; map <int, int> counts; if (k == 0) { return result; } for (auto a: arr) { counts[a]++; } for (auto it: counts) { for (int i = 0; i < it.second; i++) { result.push_back(it.first); if (result.size() == k) { return result; } } } return result; } };
题解参考:https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/jian-zhi-offer-40-zui-xiao-de-k-ge-shu-j-9yze/,大佬太强了,把快排说得好清楚,代码瞬间看懂
class Solution { public: vector<int> getLeastNumbers(vector<int>& arr, int k) { vector<int> result; if (k == 0) { return result; } else if (k >= arr.size()) { return arr; } else { quick_sort(arr, k, 0, arr.size()-1); result.assign(arr.begin(), arr.begin()+k); return result; } } void quick_sort(vector<int>& arr, int k, int left, int right) { int i = left, j = right; while(i<j) { for(; i < j && arr[j] >= arr[left]; j--); for(; i < j && arr[i] <= arr[left]; i++); swap(arr[i], arr[j]); } swap(arr[i], arr[left]); if (i == k) { return; } else if (i < k) { quick_sort(arr, k, i+1, right); } else { quick_sort(arr, k, left, i-1); } } };
注意只需要维护长度为k的堆即可(不属于前k小的元素,要么会变成堆的根,要么是在第k之后的元素),考虑到返回的是vector,我这里使用了make_heap技巧而不是priority_queue,并且这样只需要对队列头进行赋值,省去了入队出队的操作。
class Solution { public: vector<int> getLeastNumbers(vector<int>& arr, int k) { vector<int> result; if (k == 0) { return result; } else if (k >= arr.size()) { return arr; } else { result.assign(arr.begin(), arr.begin()+k); make_heap(result.begin(), result.end()); for (int i = k; i < arr.size(); i++) { if (arr[i] < result[0]) { result[0] = arr[i]; make_heap(result.begin(), result.end()); } } return result; } } };
就是时间上太慢了,试了一下,还是优先队列香
class Solution { public: vector<int> getLeastNumbers(vector<int>& arr, int k) { vector<int> result; if (k == 0) { return result; } else if (k >= arr.size()) { return arr; } else { priority_queue<int> Q; for (int i = 0; i < k; Q.push(arr[i]),i++); for (int i = k; i < arr.size(); i++) { if (arr[i] < Q.top()) { Q.pop(); Q.push(arr[i]); } } while(!Q.empty()) { result.push_back(Q.top()); Q.pop(); } return result; } } };