O (N) 의 시간 최대 K 개 찾기

N 개수 중 가장 큰 K 개 수 를 찾 는 것 은 본질 적 으로 가장 큰 K 개수 중 가장 작은 것, 즉 K 가 큰 수 를 찾 는 것 이다.2 분 검색 정책 을 사용 하여 N 개의 숫자 중 K 가 큰 숫자 를 찾 을 수 있 습 니 다.주어진 수 p 에 대해 서 는 O (N) 의 시간 복잡 도 에서 p 보다 작 지 않 은 모든 수 를 찾 을 수 있 습 니 다.k 번 째 큰 요 소 를 찾 습 니 다:

#include <iostream>
using namespace std;

//         
int partition(int a[],int l,int r)
{
    int i,j,x,temp;
    i = l;
    j = r+1;
    x = a[l];
    // >=x         
    // <=x         
    while (1)
    {
        while(a[++i] > x);
        while(a[--j] < x);
        if(i >= j) break;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    a[l] = a[j];
    a[j] = x;
    return j;
}

//      
int random_partition(int a[],int l,int r)
{
    int i = l+rand()%(r-l+1);//     
    int temp = a[i];
    a[i] = a[l];
    a[l] = temp;
    return partition(a,l,r);//      
}

//     k   
int random_select(int a[],int l,int r,int k)
{
    int i,j;
    if (l == r) //    
    {
        return a[l];
    }
    i = random_partition(a,l,r);//  
    j = i-l+1;
    if(k == j) //    ，   K   
        return a[i];
    if(k < j)
    {
        return random_select(a,l,i-1,k);//    ，        K   
    }
    else
        return random_select(a,i+1,r,k-j);//    ，        K   }

int main()
{
    int a[]={1,2,3,4,6,6,7,8,10,10};

    cout<<random_select(a,0,9,1)<<endl;
    cout<<random_select(a,0,9,5)<<endl;
    return 0;
}

만약 에 모든 N 개의 수가 정수 이 고 그들의 수치 범위 가 그리 크 지 않 으 면 신청 공간 을 고려 하여 모든 정수 가 나타 난 횟수 를 기록 한 다음 에 큰 것 에서 작은 것 으로 가장 큰 K 개 를 취 할 수 있다.예 를 들 어 모든 정수 가 (0, MAXN) 구간 에 있 으 면 하나의 배열 count [MAXN] 를 이용 하여 모든 정수 에 나타 난 개 수 를 기록 합 니 다 (count [i] 는 정수 i 가 모든 정수 에 나타 난 개 수 를 표시 합 니 다).한 번 스 캔 만 하면 count 배열 을 얻 을 수 있 습 니 다.그리고 K 번 째 큰 원 소 를 찾 아 라.

for(sumCount = 0, v = MAXN-1; v >= 0; v--)
{
    sumCount += count[v];
    if(sumCount >= K)
        break;
}
return v;

극단 적 인 상황 에서 N 개의 정수 가 각각 다 르 면 우 리 는 심지어 하나의 bit 만 이 정수 가 존재 하 는 지 (bit 비트 가 1 또는 0) 를 저장 해 야 한다. 이렇게 사용 하 는 공간 은 크게 압축 할 수 있다.
물론 계수 정렬, 통 정렬 등 O (N) 의 시간 정렬 알고리즘 을 사용 해도 K 의 큰 수 를 찾 을 수 있 지만 공간 을 시간 으로 바 꾸 는 대가 이기 도 하 다.
실제 상황 에서 모든 요소 가 정수 라 고 보장 하 는 것 이 아니 라 수치 범위 가 그리 크 지 않다.위의 방법 은 여전히 널리 사용 할 수 있다.만약 에 N 개의 숫자 중 가장 큰 숫자 인 Vmax, 가장 작은 Vmin 이 라면 우 리 는 이 구간 [Vmax, Vmin] 을 M 블록 으로 나 눌 수 있 습 니 다. 각 동네 간 의 경 계 는 d = (Vmax - Vmin) / M, 즉 [Vmin, Vmin + d], [Vmin + d, Vmin + 2d] 입 니 다. 그리고 모든 요 소 를 스 캔 하여 각 동네 간 의 요소 개 수 를 통계 하면 K 번 째 큰 요소 가 어느 동네 에 있 는 지 알 수 있 습 니 다.그리고 그 동네 에서 K 번 째 큰 수 를 찾 아 보 세 요.우 리 는 가능 한 한 큰 M 을 찾 아야 하지만, M 의 수 치 는 메모리 의 제한 을 받는다.
가장 큰 K 개 수 를 찾 아 쌓 기 를 사용 하면 이 글 을 볼 수 있 습 니 다.http://blog.csdn.net/luxiaoxun/article/details/7796368