题目描述

此题的基础解法是用快排思想，但是我用的算法加了一些优化算法，第一我不是对整个序列进行排序，假设我需要查找的第k个元素在某个区间内的时候，我才会对那个区间排序，否则直接past，因为每次排序都只会选择一个区间进行排序，按照快排的执行二叉树，可以看出该二叉树应该是一个满二叉树，我的做法是只会执行该二叉树的一个从根节点到叶子节点的路径。

if(goal - 1 <= j ) QuickSort(q, l, j);
if(goal - 1 > j) QuickSort(q, j + 1, r); 

算法1

(快排) $O(n)$

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

int goal, res;

void QuickSort(vector<int>& q, int l, int r)
{
    if(l >= r || res) return;

    int i = l - 1, j = r + 1;
    int x = q[l + r >> 1];

    while(i < j)
    {
        do i ++ ; while(q[i] < x);
        do j -- ; while(q[j] > x);
        if(i < j) swap(q[i], q[j]);
        else break;
    }
    if(goal - 1 <= j ) QuickSort(q, l, j);
    if(goal - 1 > j) QuickSort(q, j + 1, r); 
    if(j == goal - 1)  res = q[j];
    if(r == goal - 1)  res = q[r];
}

int main()
{
    int n, k;
    cin >> n >> k;
    goal = k;
    vector<int> input(n, 0);
    for(int i = 0; i < n; i ++ ) cin >> input[i];
    QuickSort(input, 0, n - 1);
    cout << res << endl;


    return 0;
}