RMQ 문제 (구간 최 값 조회)

1154 단어
구간 의 가장 큰 값 문제 라 고 불 리 는 문제 가 있 습 니 다. n 개의 요 소 를 지정 하려 면 아래 표 시 된 p, q 사이 의 최대 / 작은 값 을 조회 해 야 합 니 다.
먼저 모든 조회 에 대해 동태 적 으로 최 치 를 구 할 수 없 을 것 이 라 고 확정 했다. 매번 계산 해 야 하기 때문에 비교적 많은 시간 을 소모 할 수 있 기 때문이다.
모든 결 과 를 먼저 얻 고 조회 할 때 결 과 를 직접 꺼 내 는 것 이 좋 은 해결책 이다.이렇게 하면 모든 조 회 를 덮어 쓰 고 빠 른 색인 을 할 수 있 는 데이터 구조 가 필요 하 다.
하나의 2 차원 배열 로 중간 결 과 를 저장 합 니 다. RMQ [n] [i]. 모든 요 소 는 i + 2 ^ n 개의 요소 간 의 최대 치 를 표시 합 니 다.이렇게 해서 우 리 는 알고리즘 을 두 부분 으로 나 누 었 습 니 다. 하 나 는 초기 화 이 고 하 나 는 조회 입 니 다. 알고리즘 은 다음 과 같 습 니 다.
void prepare(int n,int *data)
{
	int i,j,k;
	for (i = 0;i <= n;mylog[i ++ ] = k)
	{
		for(k = 0;(1 << (k + 1)) < i;++ k);
	}
	
	for (j = 0;(1 << j) < n;++ j)//     n > 1        ，   n = 1            ，   table      
	{
		for (i = 0;i + (1 << j) <= n;++ i)//        ，   1 << j      1，    i     n - 1，            
		{
			if(0 == j)
			{
				table[0][i] = data[i];
			}
			else
			{
				table[j][i] = max(table[j - 1][i],table[j - 1][i + (1 << (j - 1))]);
			}
		}
	}
}

int queryMax(int p,int q)
{
	int k = mylog[q - p + 1];
	return max(table[k][p],table[k][q - (1 << k)]);
}
링크 관련 필기시험 문제 (2)
리액트 네이티브 & Expo + Node.js,NPM 란

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage