한 무더기 의 데이터 중 가장 크 거나 가장 작은 K 개 수 를 찾아내다

용량 이 K 인 최소 더미 로 최대 K 개 수 를 저장 하고, 최소 더미 의 꼭대기 요 소 는 최대 K 개 수 중 가장 작은 것 이다.새로운 요 소 를 고려 할 때마다 쌓 인 요소 와 비교 하고 쌓 인 요소 보다 클 때 만 쌓 인 요 소 를 교체 하고 최소 더 미 를 업데이트 합 니 다.시간 복잡 도 는 O (N * logK) 다.
가장 큰 K 개 수 를 찾 는 방법 은 K 개의 수가 있 는 가장 작은 무 더 기 를 만 드 는 것 이다.

#include <iostream>
#include <vector>
#include <set>

using namespace std;

typedef multiset< int,less<int> >  INTHEAP;

void FindGreatestNum(vector<int>& iArray, const unsigned int num, INTHEAP& pRes)
{
	pRes.clear();
	if(iArray.empty() || num <= 0)
	{
		return;
	}

	vector<int>::iterator iter = iArray.begin();
	while(iter != iArray.end())
	{
		if(pRes.size() < num)
		{
			pRes.insert(*iter);
		}
		else
		{
			INTHEAP::iterator pIter = pRes.begin();
			if(*iter > *pIter)
			{
				pRes.erase(pIter);
				pRes.insert(*iter); 
			}
		}
		iter ++;
	}
}
int main()
{
	int iArray[] = {1,6,9,0,2,8,12,77,90,54,78,92,23,34,56,76,91};
	int len =  sizeof( iArray ) / sizeof( int );
	const unsigned int num = 7;
	vector<int> nArray(iArray, iArray + len);

	INTHEAP pRes;
	FindGreatestNum(nArray, num, pRes);
	INTHEAP::iterator iter = pRes.begin();
	while(iter != pRes.end())
	{
		cout<<*iter<<" ";
		iter ++;
	}
	cout<<endl;
	return 0;
}

동 리: 가장 작은 K 개 수 를 찾 는 방법 은 K 개의 수가 있 는 가장 큰 무 더 기 를 만 드 는 것 이다.

#include <iostream>
#include <set>
#include <vector>

using namespace std;
typedef multiset<int, greater < int > >  intHeap;

void FindKLeastNumbers(vector< int >& iArray,const unsigned int num,intHeap& pResult)
{
	pResult.clear();
	if(iArray.empty() || num <= 0)
	{
		return;
	}
	for(vector<int>::iterator iter = iArray.begin(); iter != iArray.end(); iter ++)
	{
		if(pResult.size() < num)
		{
			pResult.insert(*iter);
		}
		else
		{
			multiset<int, greater<int> >::iterator pIter = pResult.begin();

			if(*iter < *(pResult.begin()))
			{
				pResult.erase(pIter);
				pResult.insert(*iter);
			}
		}
	}
}

int main()
{
	int iArray[]  = {1,9,7,8,5,3,9,4,2};
	int len = sizeof( iArray ) / sizeof( int );
	vector< int >  nArray(iArray, iArray + len);

	const unsigned int num = 4;
	intHeap pResult;

	FindKLeastNumbers(nArray, num, pResult);
	multiset<int, greater<int> >::iterator iter = pResult.begin();

	while(iter != pResult.end())
	{
		cout<<*iter<<" ";
		iter ++;
	}
	cout<<endl;
	return 0;

}

소결: STL 과 관련 된 지식 을 배 우 는 것 을 통 해 이것 은 아주 좋 은 라 이브 러 리 이 고 좋 은 데이터 구 조 를 가 지 며 운영 효율 도 비교적 높 기 때문에 안에서 파악 해 야 할 중요 한 기술 이다.