중위 수 와 순서 통계
순서 통계 가 있 으 면 중위 수 를 구 하 는 것 이 편리 하 다.배열 에 n 개의 요소 가 있다 고 가정 하고 n 이 홀수 라면 제 (n + 1) / 2 작은 요소 로 전환 합 니 다.n 이 짝수 라면 n / 2 작은 것 과 n / 2 + 1 작은 요 소 를 구하 고 평균 적 으로 가치 가 있 습 니 다.
중위 수의 장점?평균 치 를 구 할 때의 단점 을 해결 하기 위해 서 인 것 같다. 만약 에 견본 에 큰 값 이 있 으 면 다른 대부분 은 보통 값 이 고 평균 치 를 구 하 는 것 은 실제 상황 에 비해 오차 가 매우 크다.이 때 는 중위 수 를 사용 하 는 것 이 좋다.(뭐라고? 최대 치가 배열 중간 에 있다 고? 그 건 RP 문제 야. > <)
========================
순차 통계 계산법
========================
1. 기본 사상 빠 른 정렬 중의 분 치 법 을 참고 하여 모든 라운드 에서 보초병 보다 작은 요 소 를 보초병 앞 에 놓 고 보초병 보다 큰 요 소 를 보초병 뒤에 놓는다.보초병 과 같은 원소 의 개수 n 보다 작은 것 은 순서 i 와 관련 이 있다 는 점 을 이용 하여 분 단 된 어느 쪽 에 연결 하여 끊 임 없 는 테스트 를 한다.
2. 알고리즘 설명
빠 른 정렬 과 유사 합 니 다. 본 블 로그 의 다른 글 인 '정렬 알고리즘 요약' 을 보십시오.하지만 한 가지 분명 하지 않 습 니 다. 프로그램 에 표시 되 어 있 습 니 다. 해답 을 바 랍 니 다. 감사합니다.
3. 복잡 도
공간 복잡 도 O (1), 시간 복잡 도 는 O (n) 로 빠 른 정렬 에 비해 분 단 된 측면 에서 만 연산 하기 때문이다.
4. 알고리즘 구현
template<typename T>
int partition(T * array, const int low, const int high)
{
//select the first elem as pivot. Here use random index for pivot will be better
T pivot = array[low];
for(int i=low, j=high; i<j;)
{
//scan for the first elem that smaller than pivot
while(j>i && array[j]>=pivot)
j--;
if(i<j)
{
//since array[i] is already be array[j] which is smaller than pivot,
//array[i+1] will firstly checkde in next scan
array[i++] = array[j];
}
//scan for the first elem that bigger than pivot
while(i<j && array[i]<=pivot)
i++;
if(i<j)
{
array[j--] = array[i];
}
}
//put the pivot to right position, pls notice that i will be equal with j at this point
array[i] = pivot;
return i;
}
template<typename T>
T order_select(T *array, const int low, const int high, const int order)
{
if(low == high) // ？ ， ，
return array[low];
int pivot_index = partition(array, low, high);
// ( ) n
int leftSegLength = pivot_index - low + 1;
// n， i ( )
if(order <= leftSegLength)
{
return order_select(array, low, pivot_index, order);
}
else
{
return order_select(array, pivot_index+1, high, order-leftSegLength);
}
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
