무질서한 그룹 중 K번째로 큰 숫자 찾기

아이디어:

빠른 순서의 구분 사상을 이용하여 앞의 k대수를 찾아낸 다음에 K원소를 찾을 때까지 끊임없이 구분할 수 있다

코드:

#include 
#include 
#include 5
using namespace std;
int findK(int left, int right, int arr[], int k) {
    if(left >= right) return arr[left];
    int first = left, last = right;
    int key = arr[first];
    while(first < last) {
        while(first < last && arr[last] >= key) last--;
        arr[first] = arr[last];
        while(first < last && arr[first] <= key) first++;
        arr[last] = arr[first];
    }
    arr[first] = key;
    if(first == k) return arr[k];
    else {
        if(first > k) return findK(left, first, arr, k);
        else return findK(first+1, right, arr, k);
    }
}
int main()
{
    int n;
    int arr[1000];

    scanf("%d", &n);
    for(int i = 1; i <= n; i++) cin >>arr[i];
    int k;
    cin >> k;
    int num = findK(1, n, arr, k);
    cout << num << endl;
    return 0;
}

 
전재 대상:https://www.cnblogs.com/GHzcx/p/9634210.html