请大佬 看下这个滴滴编程题

#include <iostream> #include <vector> #include <algorithm> #include <set> #include <sstream> using namespace std; int partition(vector<int> &arr, int i, int j) {     int I = i;     while (i < j)     {         while (i < j && arr[j] >= arr[I]) --j;         while (i < j && arr[i] <= arr[I]) ++i;         if (i < j) std::swap(arr[i], arr[j]);     }     std::swap(arr[i], arr[I]);     return i; } int get_least_k(vector<int> &vec_input, int k) {     int n = vec_input.size();     if (n == 0 || k <= 0 || k > n)         return 0;     int start_index = 0;     int end_index = n - 1;     int index = partition(vec_input, start_index, end_index);     while (index != k - 1) // 当分划元素的下标是k-1时，意味着前k-1个数比次数小(不大于)，后边的数比次数大(不小于)     {         if (index > k - 1)             index = partition(vec_input, start_index, index - 1);         else if (index <= k - 1)             index = partition(vec_input, index + 1, end_index);     }     return vec_input[index]; } int main() {     vector<int> vec_num;     int val;     string line;     stringstream ss;     getline(cin, line);     ss.clear();     ss << line;     while (!ss.eof())     {         ss >> val;         vec_num.push_back(val);     }     int k;     cin >> k;     cout << get_least_k(vec_num,vec_num.size() + 1 - k) << endl;     return 0; }

作者：liantieyu 链接：https://www.nowcoder.com/discuss/35115 来源：牛客网 我之前用C++写的答案，不能完全AC，怎么也解决不了。 后来一怒之下换了python，同样最基本的思路，逆排序，取第k位，就100%了。 感觉还是自己C++太菜，或者题目用c++写有坑？？ 附上我的python代码： nums = [int(x) for x in input().strip().split()] k = [int(x) for x in input().strip().split()][0] nums = sorted(nums, reverse=True) print(nums)

#include<iostream> #include<vector> using namespace std; int Partition11(vector<int> &data, int start, int end); int KLeastNumbers(vector<int> &data,int k); int main() { vector<int> a; int m; int k; while (cin >> m) { a.push_back(m); if (cin.get() == '\n') break; } cin >> k; cout << KLeastNumbers(a, k); return 0; } int KLeastNumbers(vector<int> &data, int k) { if (data.size()==0|| k <= 0) return -1; int len = data.size(); int index = Partition11(data, 0, len - 1); while (index != k - 1) { if (index > k - 1) index = Partition11(data, 0, index - 1); if (index < k - 1) index = Partition11(data, index + 1, len - 1); } return data[index]; } int Partition11(vector<int> &data, int start, int end) { int index = data[start]; int i = start + 1; int j = end; while (true) { while (data[i] > index) { i++; if (i == end) break; } while (index >= data[j]) { j--; if (j == start) break; } if (i >= j) break; swap(data[i], data[j]); } swap(data[start], data[j]); return j; }

去重之前，40%的通过率，去重之后60%的通过率！！！郁闷啊

不能去重

乱写的就通过了，感觉你们写的很高大上

直接冒泡排序，没做优化。 要优化的话估计改一下快排就可以。

为什么都在讨论用什么排序，感觉sort就可以了啊。。。。

就sort再输出k-1索引的数就AC了啊

Array.sort(arr); 然后直接输出arr[arr.length+1-k];    暴力AC结束！

感觉可以直接用c++ STL中的nth_element，不知道算不算犯规

直接用STL的排序sort返回第k大的数，AC了