优化递归算法在该题的时间损耗

Question

#include<iostream>
#include<cstdlib>
using namespace std;
void SwAp(int &a,int &b){
    int tmp=a;
    a=b;
    b=tmp;
}
int FindKthLargest(int *num,int k,int left,int right){
    int base=num[left];//基准数
    int L=left,R=right;
    while(1){
        while((left<=right)&&(base<=num[left])) left++;
        while((left<right)&&base>num[right]) right--;
        if(left<right){
            SwAp(num[left],num[right]);
        }else break;
    }
    SwAp(num[left-1],num[L]);
    if((left-L-1)>=k) return FindKthLargest(num,k,L,left-2);
    else if((left-L-1)<k-1) return FindKthLargest(num,k-(left-L-1)-1,left,R);
    else return base;
}
int main(){
    int N,k;
    while(cin>>N>>k){
        int *num=(int *)malloc(N*sizeof(int));
        for(int i=0;i<N;i++){
            cin>>num[i];
            if(i+1>=k){
                int result=FindKthLargest(num,k,0,i);
                cout<<result<<endl;
            }
        }
        free(num);   
    }
    return 0;
}

Answer 1

这题用优先队列做更简单

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main()
{
    int n, k;
    while (cin >> n >> k)
    {
        vector<int> a(n);
        for (int i = 0; i < n; i++)
            cin >> a[i];
        priority_queue<int, vector<int>, std::greater<int>> queue;
        for (int i = 0; i < k; i++)
            queue.push(a[i]);
        cout << queue.top() << '\n';
        for (int i = k; i < n; i++)
        {
            queue.push(a[i]);
            queue.pop();
            cout << queue.top() << '\n';
        }
    }
    return 0;
}