영 씨 행렬
만약 에 행렬 의 모든 줄 이 엄격 하고 단조 로 워 지면 우 리 는 이 행렬 을 양 씨 행렬(Young Tableau)이 라 고 부른다.양 씨 행렬(a[m][n])에 대해 보통 두 가지 문제 와 관련된다.(1)양 씨 행렬 에서 어떤 요소 X 를 어떻게 찾 습 니까?(2)어떻게 양 씨 행렬 에서 k 번 째 큰 수 를 찾 습 니까?
2.해결 방안
양 씨 행렬 은 매우 교묘 한 데이터 구조 로 쌓 을 수도 있 고 균형 트 리 로 도 사용 할 수 있다.
(1)문제 1 풀이
[방안 1]
<이분 찾기>
양 씨 행렬 에 대해 모든 줄 이 질서 가 있 기 때문에 행렬 에서 2 분 으로 찾 을 수 있다.구체 적 인 방법 은:
현재 서브 매트릭스 a[i][j]~a[s][t]에 대해 중간 요 소 는 a[(i+s)/2][(j+t)/2]이 고 a[(i+s)/2][(j+t)/2]=x 라면 이 요 소 를 찾 습 니 다.만약 a[(i+s)/2][(j+t)/2]>x 라면 하위 매트릭스 a[i]~a[(i+s)/2][(j+t)/2]에서 찾 습 니 다.만약 a[(i+s)/2][(j+t)/2]
<클래스 찾기>
양 씨 행렬 은 뚜렷 한 퇴적 특징 을 가지 고 있다.행렬 의 오른쪽 상단 에서 출발 하여(왼쪽 하단 에서 출발 하여 사고방식 이 유사 하 다)원소 a[i][j]에 대해 a[i][j]==x 를 찾 으 면 원소 x 를 찾 아 바로 돌아간다.a[i][j]>x 가 아래로 이동 하면 a[i+1][j]와 x 를 계속 비교 합 니 다.만약 a[i][j]
bool find_in_YoungTableau(int** a, int m, int n, int x) {
assert(a != NULL && m > 0 && n > 0);
int row, col;
row = 0;
col = n-1;
while(row <= m-1 && col >= 0) {
if(a[row][col] == x)
return true;
else if(a[row][col] > x)
col--;
else
row++;
}
return false;
}
(2)문제 2 풀이
[방안 1]
<작은 지붕 쌓 기 법>
먼저 a[0][0]을 작은 지붕 더미 에 넣 은 다음 에 작은 지붕 더미 에서 최소 요 소 를 꺼 내 고 이 요소 보다 크 고 인접 한 두 가지 요소(a[0][0]에 대해 a[0][1]과 a[1][0]을 넣 어야 한다.두 번 째 요 소 를 꺼 낼 때 까지 추가 공간 으로 특정한 요소 가 작은 지붕 더미 에 넣 었 는 지 기록 하여 중복 가입 을 방지 해 야 한다.
[방안 2]
<이분 매 거+클래스 찾기>
먼저,2 분 매 거 진 숫자 x 를 찾 았 는데 이것 은 양 씨 행렬 의 k 개 보다 크다.그리고 클래스 검색 법 을 이용 하여 x 보다 작은 요 소 를 찾 습 니 다.이 알고리즘 은 시간 복잡 도 는 O(m+n)lg(mn)이지 만 추가 저장 공간 이 필요 없습니다.코드 는 다음 과 같 습 니 다:
int find_kth_in_YoungTableau(int** a, int m, int n, int k) {
int low = a[0][0];
int high = a[m-1][n-1];
int order = 0;
int mid = 0;
do {
mid = (low + high) >> 1;
order = get_order(a, m, n, mid);
if(order == k)
break;
else if(order > k)
high = mid - 1;
else
low = mid + 1;
} while(1); // ， k mid
int row = 0;
int col = n - 1;
int ret = mid;
while(row <= m-1 && col >= 0) { // mid
if(a[row][col] < mid) {
ret = (a[row][col] > ret) ? a[row][col] : ret;
row++;
} else {
col--;
}
}
return ret;
}
// k
int get_order(int** a, int m, int n, int k) {
int row, col, order;
row = 0;
col = n-1;
order = 0;
while(row <= m-1 && col >= 0) {
if(a[row][col] < k) {
order += col + 1;
row++;
} else {
col--;
}
}
return order;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
