题目描述
使用了一种和模板不同的快排方式进行解答。但发现在LeetCode上的排名很低,不太明白为什么
算法
时间复杂度 $O(n)$
C++ 代码
#include <bits/stdc++.h>
using namespace std;
int nums[100010];
int n, k;
int quick_sort(int nums[], int l, int r, int k) {
if (l == r-1) return nums[l];
int pivot = nums[r-1];
int cur = l;
for (int i = l; i < r-1; i++) {
if (nums[i] < pivot) {
swap(nums[cur++], nums[i]);
}
}
swap(nums[cur], nums[r-1]);
int sl = cur - l + 1;
if (sl > k) {
return quick_sort(nums, l, cur, k);
}
else if (sl < k) {
return quick_sort(nums, cur+1, r, k-sl);
}
else {
return nums[cur];
}
}
int main() {
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
cout<<quick_sort(nums, 0, n, k);
}
LeetCode时间
第 $k$ 小问题是有严格 $O(n)$ 时间复杂度的解法的,这个方法不是严格 $O(n)$ 的,严格 $O(n)$ 的算法应该是 median of median 算法。
好的,谢谢解答。