왼쪽에서 오른쪽으로, 위에서 아래로 정렬 된 2D 배열에서 숫자를 어떻게 검색합니까?
최근에이 인터뷰 질문을 받았는데 그에 대한 좋은 해결책이 무엇인지 궁금합니다.
배열의 모든 숫자가 왼쪽에서 오른쪽으로, 위에서 아래로 증가하는 2d 배열이 있다고 가정 해 보겠습니다.
대상 번호가 어레이에 있는지 검색하고 확인하는 가장 좋은 방법은 무엇입니까?
이제 내 첫 번째 경향은 내 데이터가 정렬되어 있기 때문에 이진 검색을 활용하는 것입니다. 숫자가 O (log N) 시간에 단일 행에 있는지 확인할 수 있습니다. 그러나 나를 쫓아내는 것은 두 가지 방향입니다.
내가 효과가 있다고 생각한 또 다른 해결책은 중간에서 시작하는 것입니다. 중간 값이 내 목표보다 작 으면 중간에서 매트릭스의 왼쪽 정사각형 부분에 있는지 확인할 수 있습니다. 그런 다음 대각선으로 이동하고 다시 확인하여 대상 번호를 다듬을 때까지 대상이 잠재적으로 들어갈 수있는 사각형의 크기를 줄입니다.
누구든지이 문제를 해결하는 데 좋은 아이디어가 있습니까?
배열 예 :
왼쪽에서 오른쪽, 위에서 아래로 정렬됩니다.
1 2 4 5 6
2 3 5 7 8
4 6 8 9 10
5 8 9 10 11
다음은 간단한 접근 방식입니다.
- 왼쪽 하단에서 시작합니다.
- 목표가 그 값보다 작 으면 우리 위에 있어야하므로 하나 위로 이동 하십시오 .
- 그렇지 않으면 대상이 해당 열에있을 수 없다는 것을 알고 있으므로 오른쪽으로 이동하십시오 .
- 이동 2.
를 들어 NxM배열이 실행됩니다 O(N+M). 더 잘하기 어려울 것 같아요. :)
편집 : 많은 좋은 토론. 나는 위의 일반적인 경우에 대해 이야기하고있었습니다. 분명히, 작 N거나 M작 다면 이진 검색 접근 방식을 사용하여 로그 시간에 접근하는 무언가를 수행 할 수 있습니다.
궁금한 분들을위한 세부 정보는 다음과 같습니다.
역사
이 간단한 알고리즘을 새들백 검색 이라고합니다 . 한동안 사용되어 왔으며 N == M. 일부 참조 :
그러나, N < M직관은 이진 검색이 다음보다 더 잘 할 수 있어야한다고 제안합니다 O(N+M). 예를 들어, N == 1순수 이진 검색은 선형 시간이 아닌 로그로 실행됩니다.
최악의 경우
Richard Bird는 2006 년 논문에서 이진 검색이 Saddleback 알고리즘을 향상시킬 수 있다는 직관을 조사했습니다.
- Richard S. Bird, Improving Saddleback Search : A Lesson in Algorithm Design , in Mathematics of Program Construction, pp. 82--89, volume 4014, 2006 .
다소 특이한 대화 기법을 사용하여 Bird는에 대한 N <= M이 문제의 하한이 Ω(N * log(M/N)). 이 경계는 우리에게 선형 성능을 제공 N == M하고 N == 1.
직사각형 배열에 대한 알고리즘
행 단위 이진 검색을 사용하는 한 가지 접근 방식은 다음과 같습니다.
- 직사각형 배열로 시작하십시오
N < M.N행과M열 이라고합시다 . - 에 대한 중간 행에서 이진 검색을 수행합니다
value. 우리가 그것을 찾으면 우리는 끝난 것입니다. - 그렇지 않으면 인접한 숫자 쌍
s과g, wheres < value < g. - 위와 왼쪽에있는 숫자의 사각형
s은보다 작value으므로 제거 할 수 있습니다. - 의 오른쪽 아래에있는 사각형
g이보다 크므로value제거 할 수 있습니다. - 나머지 두 직사각형 각각에 대해 (2) 단계로 이동합니다.
최악의 복잡성 측면에서이 알고리즘은 log(M)가능한 솔루션의 절반을 제거한 다음 두 개의 작은 문제에 대해 자신을 두 번 재귀 적으로 호출합니다. log(M)모든 행에 대해 더 작은 버전의 작업 을 반복해야 하지만 , 행 수가 열 수에 비해 적 으면 로그 시간에 해당 열을 모두 제거 할 수있는 것이 가치가 있기 시작합니다 .
이것은 알고리즘에 T(N,M) = log(M) + 2 * T(M/2, N/2)Bird가 보여주는 복잡성을 제공합니다 O(N * log(M/N)).
Craig Gidney가 게시 한 또 다른 접근 방식은 위의 접근 방식과 유사한 알고리즘을 설명합니다 M/N. 단계 크기를 사용하여 한 번에 행을 검사합니다 . 그의 분석은 이것이 O(N * log(M/N))성능에도 영향을 미친다는 것을 보여줍니다 .
성능 비교
Big-O 분석은 모두 훌륭하고 좋지만 이러한 접근 방식이 실제로 얼마나 잘 작동합니까? 아래 차트는 점점 더 "정사각형"배열에 대한 네 가지 알고리즘을 검사합니다.
( "순진"알고리즘은 단순히 어레이의 모든 요소를 검색합니다. "재귀"알고리즘은 위에 설명되어 있습니다. "하이브리드"알고리즘은 Gidney 알고리즘을 구현 한 것입니다 . 각 어레이 크기에 대해 각 알고리즘을 고정 세트에 타이밍하여 측정했습니다. 무작위로 생성 된 배열 1,000,000 개)
몇 가지 주목할 점 :
- 예상대로 "이진 검색"알고리즘은 직사각형 배열에서 최고의 성능을 제공하고 Saddleback 알고리즘은 정사각형 배열에서 가장 잘 작동합니다.
- Saddleback 알고리즘은 아마도 각 항목에 대해 다중 비교를 수행하기 때문에 1-d 배열의 "순진한"알고리즘보다 성능이 떨어집니다.
- "이진 검색"알고리즘이 정사각형 배열에 미치는 성능 저하는 아마도 반복되는 이진 검색을 실행하는 오버 헤드 때문일 것입니다.
요약
이진 검색을 영리하게 사용 O(N * log(M/N)하면 직사각형 및 정사각형 배열 모두에 성능을 제공 할 수 있습니다 . O(N + M)"안장"알고리즘은 매우 간단하지만 성능 저하의 배열과 같은 겪고있다 점점 직사각형이된다.
이 문제는 소요 Θ(b lg(t))시간 b = min(w,h)과 t=b/max(w,h). 이 블로그 게시물 에서 솔루션에 대해 논의합니다 .
하한
공격자는 Ω(b lg(t))자신을 주 대각선으로 제한 하여 알고리즘이 쿼리 를 만들도록 강제 할 수 있습니다 .
범례 : 흰색 셀은 작은 항목, 회색 셀은 큰 항목, 노란색 셀은 작거나 같은 항목, 주황색 셀은 크거나 같은 항목입니다. 공격자는 알고리즘이 쿼리가 지속되는 노란색 또는 주황색 셀이되도록 솔루션을 강제합니다.
공지 사항이 있다는 것을 b크기의 독립적 인 정렬 된 목록을 t필요로 Ω(b lg(t))완전히 제거하기 위해 쿼리.
연산
- (일반성을 잃지 않고 가정
w >= h) - 대상 항목을
t유효한 영역의 오른쪽 상단 모서리 왼쪽 에있는 셀과 비교합니다.- 셀의 항목이 일치하면 현재 위치를 반환합니다.
- 셀 항목이 대상 항목보다 작 으면
t이진 검색을 사용하여 행 의 나머지 셀을 제거합니다 . 이 작업을 수행하는 동안 일치하는 항목이 발견되면 해당 위치로 돌아갑니다. - 그렇지 않으면 셀의 항목이 대상 항목보다 많아
t짧은 열이 제거 됩니다.
- 유효한 영역이 남아 있지 않으면 실패를 반환합니다.
- 2 단계로 이동
항목 찾기 :
항목이 존재하지 않는지 확인 :
범례 : 흰색 셀은 작은 항목, 회색 셀은 큰 항목, 녹색 셀은 동일한 항목입니다.
분석
b*t제거 할 짧은 열 이 있습니다 . b제거 할 긴 행 이 있습니다 . 긴 행을 제거하면 O(lg(t))시간이 걸립니다. t짧은 컬럼을 제거하면 O(1)시간이 걸립니다.
최악의 경우 모든 열과 행을 제거해야하므로 시간이 걸립니다 O(lg(t)*b + b*t*1/t) = O(b lg(t)).
lg1 이상의 결과에 대한 클램프를 가정 하고 있습니다 (예 :) lg(x) = log_2(max(2,x)). 그래서 w=h, 의미 t=1, 우리는 O(b lg(1)) = O(b) = O(w+h).
암호
public static Tuple<int, int> TryFindItemInSortedMatrix<T>(this IReadOnlyList<IReadOnlyList<T>> grid, T item, IComparer<T> comparer = null) {
if (grid == null) throw new ArgumentNullException("grid");
comparer = comparer ?? Comparer<T>.Default;
// check size
var width = grid.Count;
if (width == 0) return null;
var height = grid[0].Count;
if (height < width) {
var result = grid.LazyTranspose().TryFindItemInSortedMatrix(item, comparer);
if (result == null) return null;
return Tuple.Create(result.Item2, result.Item1);
}
// search
var minCol = 0;
var maxRow = height - 1;
var t = height / width;
while (minCol < width && maxRow >= 0) {
// query the item in the minimum column, t above the maximum row
var luckyRow = Math.Max(maxRow - t, 0);
var cmpItemVsLucky = comparer.Compare(item, grid[minCol][luckyRow]);
if (cmpItemVsLucky == 0) return Tuple.Create(minCol, luckyRow);
// did we eliminate t rows from the bottom?
if (cmpItemVsLucky < 0) {
maxRow = luckyRow - 1;
continue;
}
// we eliminated most of the current minimum column
// spend lg(t) time eliminating rest of column
var minRowInCol = luckyRow + 1;
var maxRowInCol = maxRow;
while (minRowInCol <= maxRowInCol) {
var mid = minRowInCol + (maxRowInCol - minRowInCol + 1) / 2;
var cmpItemVsMid = comparer.Compare(item, grid[minCol][mid]);
if (cmpItemVsMid == 0) return Tuple.Create(minCol, mid);
if (cmpItemVsMid > 0) {
minRowInCol = mid + 1;
} else {
maxRowInCol = mid - 1;
maxRow = mid - 1;
}
}
minCol += 1;
}
return null;
}
이 문제에 대해 여러분이 제안한 것과 유사한 분할 및 정복 전략을 사용하지만 세부 사항이 약간 다릅니다.
이것은 행렬의 하위 범위에 대한 재귀 검색입니다.
각 단계에서 범위 중간에있는 요소를 선택합니다. 찾은 값이 찾고있는 것이면 완료된 것입니다.
그렇지 않고 발견 된 값이 찾고있는 값보다 작 으면 현재 위치의 위와 왼쪽에있는 사분면에 없다는 것을 알 수 있습니다. 따라서 두 하위 범위를 재귀 적으로 검색합니다. 현재 위치 아래에있는 모든 것 (배타적으로)과 현재 위치에 있거나 위에있는 오른쪽에있는 모든 것 (배타적으로)입니다.
그렇지 않으면 (찾은 값이 찾고있는 값보다 큽니다) 현재 위치의 오른쪽 아래 사분면에 없다는 것을 알고 있습니다. 따라서 두 하위 범위를 재귀 적으로 검색합니다. 현재 위치의 왼쪽에있는 모든 항목 (배타적)과 현재 열 또는 오른쪽의 열에있는 현재 위치 위의 모든 항목 (배타적)을 검색합니다.
그리고 ba-da-bing, 당신은 그것을 찾았습니다.
각 재귀 호출은 현재 위치 위의 모든 행이 아닌 현재 하위 범위 만 처리합니다. 현재 하위 범위에있는 것들만.
다음은 몇 가지 의사 코드입니다.
bool numberSearch(int[][] arr, int value, int minX, int maxX, int minY, int maxY)
if (minX == maxX and minY == maxY and arr[minX,minY] != value)
return false
if (arr[minX,minY] > value) return false; // Early exits if the value can't be in
if (arr[maxX,maxY] < value) return false; // this subrange at all.
int nextX = (minX + maxX) / 2
int nextY = (minY + maxY) / 2
if (arr[nextX,nextY] == value)
{
print nextX,nextY
return true
}
else if (arr[nextX,nextY] < value)
{
if (numberSearch(arr, value, minX, maxX, nextY + 1, maxY))
return true
return numberSearch(arr, value, nextX + 1, maxX, minY, nextY)
}
else
{
if (numberSearch(arr, value, minX, nextX - 1, minY, maxY))
return true
reutrn numberSearch(arr, value, nextX, maxX, minY, nextY)
}
지금까지 제시된 두 가지 주요 답변은 O(log N)"지그재그 방법"과O(N+M) 이진 검색 방법 인 것 같습니다. 나는 두 가지 방법을 다양한 설정과 비교하여 몇 가지 테스트를 할 것이라고 생각했습니다. 세부 사항은 다음과 같습니다.
배열은 모든 테스트에서 N x N 정사각형이며 N은 125에서 8000까지 다양합니다 (제 JVM 힙이 처리 할 수있는 가장 큰 것). 각 배열 크기에 대해 배열에서 임의의 위치를 선택하여 단일 2. 그런 다음 3가능한 모든 곳에 (2의 오른쪽과 아래에) 배치 한 다음 나머지 배열을 채웠습니다.1. 일부 이전 댓글 작성자는 이러한 유형의 설정이 두 알고리즘 모두에 대해 최악의 런타임을 생성 할 것이라고 생각하는 것 같습니다. 각 어레이 크기에 대해 2 (검색 대상)에 대해 100 개의 서로 다른 임의 위치를 선택하고 테스트를 실행했습니다. 각 알고리즘에 대해 평균 실행 시간과 최악의 실행 시간을 기록했습니다. Java에서 좋은 ms 판독 값을 얻기에는 너무 빨라서 Java의 nanoTime ()을 신뢰하지 않기 때문에 항상 균일 한 바이어스 요소를 추가하기 위해 각 테스트를 1000 번 반복했습니다. 결과는 다음과 같습니다.
ZigZag는 평균 및 최악의 경우 모든 테스트에서 바이너리를 이겼지 만, 모두 서로 어느 정도의 크기 내에 있습니다.
다음은 Java 코드입니다.
public class SearchSortedArray2D {
static boolean findZigZag(int[][] a, int t) {
int i = 0;
int j = a.length - 1;
while (i <= a.length - 1 && j >= 0) {
if (a[i][j] == t) return true;
else if (a[i][j] < t) i++;
else j--;
}
return false;
}
static boolean findBinarySearch(int[][] a, int t) {
return findBinarySearch(a, t, 0, 0, a.length - 1, a.length - 1);
}
static boolean findBinarySearch(int[][] a, int t,
int r1, int c1, int r2, int c2) {
if (r1 > r2 || c1 > c2) return false;
if (r1 == r2 && c1 == c2 && a[r1][c1] != t) return false;
if (a[r1][c1] > t) return false;
if (a[r2][c2] < t) return false;
int rm = (r1 + r2) / 2;
int cm = (c1 + c2) / 2;
if (a[rm][cm] == t) return true;
else if (a[rm][cm] > t) {
boolean b1 = findBinarySearch(a, t, r1, c1, r2, cm - 1);
boolean b2 = findBinarySearch(a, t, r1, cm, rm - 1, c2);
return (b1 || b2);
} else {
boolean b1 = findBinarySearch(a, t, r1, cm + 1, rm, c2);
boolean b2 = findBinarySearch(a, t, rm + 1, c1, r2, c2);
return (b1 || b2);
}
}
static void randomizeArray(int[][] a, int N) {
int ri = (int) (Math.random() * N);
int rj = (int) (Math.random() * N);
a[ri][rj] = 2;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (i == ri && j == rj) continue;
else if (i > ri || j > rj) a[i][j] = 3;
else a[i][j] = 1;
}
}
}
public static void main(String[] args) {
int N = 8000;
int[][] a = new int[N][N];
int randoms = 100;
int repeats = 1000;
long start, end, duration;
long zigMin = Integer.MAX_VALUE, zigMax = Integer.MIN_VALUE;
long binMin = Integer.MAX_VALUE, binMax = Integer.MIN_VALUE;
long zigSum = 0, zigAvg;
long binSum = 0, binAvg;
for (int k = 0; k < randoms; k++) {
randomizeArray(a, N);
start = System.currentTimeMillis();
for (int i = 0; i < repeats; i++) findZigZag(a, 2);
end = System.currentTimeMillis();
duration = end - start;
zigSum += duration;
zigMin = Math.min(zigMin, duration);
zigMax = Math.max(zigMax, duration);
start = System.currentTimeMillis();
for (int i = 0; i < repeats; i++) findBinarySearch(a, 2);
end = System.currentTimeMillis();
duration = end - start;
binSum += duration;
binMin = Math.min(binMin, duration);
binMax = Math.max(binMax, duration);
}
zigAvg = zigSum / randoms;
binAvg = binSum / randoms;
System.out.println(findZigZag(a, 2) ?
"Found via zigzag method. " : "ERROR. ");
//System.out.println("min search time: " + zigMin + "ms");
System.out.println("max search time: " + zigMax + "ms");
System.out.println("avg search time: " + zigAvg + "ms");
System.out.println();
System.out.println(findBinarySearch(a, 2) ?
"Found via binary search method. " : "ERROR. ");
//System.out.println("min search time: " + binMin + "ms");
System.out.println("max search time: " + binMax + "ms");
System.out.println("avg search time: " + binAvg + "ms");
}
}
이것은 문제의 하한에 대한 짧은 증거입니다.
선형 시간보다 더 잘 할 수는 없습니다 (요소 수가 아니라 배열 차원 측면에서). 아래 배열에서로 표시된 각 요소 *는 5 개 또는 6 개 (다른 요소와 는 독립적) 일 수 있습니다. 따라서 목표 값이 6 (또는 5)이면 알고리즘은 모든 값을 검사해야합니다.
1 2 3 4 *
2 3 4 * 7
3 4 * 7 8
4 * 7 8 9
* 7 8 9 10
물론 이것은 더 큰 어레이로 확장됩니다. 이것은 이 답변 이 최적 임을 의미합니다 .
업데이트 : Jeffrey L Whitledge가 지적했듯이 실행 시간 대 입력 데이터 크기 (단일 변수로 처리됨)에 대한 점근 적 하한으로 만 최적입니다. 두 배열 차원에서 두 변수 함수로 처리되는 실행 시간을 개선 할 수 있습니다.
여기에 답이 있다고 생각하며 모든 종류의 정렬 된 행렬에서 작동합니다.
bool findNum(int arr[][ARR_MAX],int xmin, int xmax, int ymin,int ymax,int key)
{
if (xmin > xmax || ymin > ymax || xmax < xmin || ymax < ymin) return false;
if ((xmin == xmax) && (ymin == ymax) && (arr[xmin][ymin] != key)) return false;
if (arr[xmin][ymin] > key || arr[xmax][ymax] < key) return false;
if (arr[xmin][ymin] == key || arr[xmax][ymax] == key) return true;
int xnew = (xmin + xmax)/2;
int ynew = (ymin + ymax)/2;
if (arr[xnew][ynew] == key) return true;
if (arr[xnew][ynew] < key)
{
if (findNum(arr,xnew+1,xmax,ymin,ymax,key))
return true;
return (findNum(arr,xmin,xmax,ynew+1,ymax,key));
} else {
if (findNum(arr,xmin,xnew-1,ymin,ymax,key))
return true;
return (findNum(arr,xmin,xmax,ymin,ynew-1,key));
}
}
흥미로운 질문입니다. 이 아이디어를 고려하십시오-모든 숫자가 목표보다 큰 경계를 만들고 모든 숫자가 목표보다 작은 경계를 만드십시오. 둘 사이에 아무것도 남지 않으면 그것이 당신의 목표입니다.
귀하의 예에서 3을 찾고 있다면 4가 될 때까지 첫 번째 행을 읽은 다음 3보다 큰 가장 작은 인접 숫자 (대각선 포함)를 찾습니다.
12 4 5 6
2 3 5 78
4 6 8 9 10
5 8 9 10 11
이제 3보다 작은 숫자에 대해서도 똑같이합니다.
1 2 3 4 5 6
2 3 5 7 8
4 6 8 9 10
5 8 9 10 11
이제 두 경계 안에있는 것이 있습니까? 그렇다면 3이되어야합니다. 그렇지 않으면 3이 없습니다. 실제로 숫자를 찾지 못하기 때문에 간접적으로 숫자가 있어야한다고 추론합니다. 이것은 모든 3을 세는 추가 보너스가 있습니다.
나는 이것을 몇 가지 예에서 시도했지만 정상적으로 작동하는 것 같습니다.
배열의 대각선을 통한 이진 검색이 가장 좋은 옵션입니다. 요소가 대각선의 요소보다 작거나 같은지 확인할 수 있습니다.
A. 대상 번호가있을 수있는 라인에서 이진 검색을 수행하십시오.
B. 그래프로 만들기 : 항상 방문하지 않은 가장 작은 이웃 노드를 취하고 너무 큰 숫자가 발견되면 역 추적하여 숫자를 찾습니다.
이진 검색이 가장 좋은 방법입니다. 1/2 x부터 1/2 y는 반으로 자릅니다. IE 5x5 정사각형은 x == 2 / y == 3과 같습니다. 목표 값의 방향에서 더 나은 영역으로 하나의 값을 반올림하고 하나의 값을 반올림했습니다.
명확성을 위해 다음 반복은 x == 1 / y == 2 OR x == 3 / y == 5
우선 사각형을 사용한다고 가정 해 보겠습니다.
1 2 3
2 3 4
3 4 5
1. 사각형 검색
대각선에서 이진 검색을 사용합니다. 목표는 목표 수보다 엄격히 낮지 않은 작은 수를 찾는 것입니다.
내가 찾고 있어요 말해 4, 예를 들어, 그때의 위치를 끝낼 것이다 5에 (2,2).
그런 다음 4테이블에있는 경우 (x,2)또는 in (2,x)과 함께 위치에 있다고 확신합니다 . 음, 그것은 단지 2 개의 이진 검색입니다.x[0,2]
복잡성은 어렵지 않습니다. O(log(N))(길이 범위에 대한 3 개의 이진 검색 N)
2. 직사각형 탐색, 순진한 접근
물론, 그것은 조금 더 복잡 할 때 도착 N과 M(사각형과) 다른,이 타락한 경우를 고려 :
1 2 3 4 5 6 7 8
2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17
그리고 제가 찾고 있다고 가정 해 봅시다 9. 대각선 접근 방식은 여전히 좋지만 대각선의 정의는 변경됩니다. 여기 내 대각선은 [1, (5 or 6), 17]입니다. 내가 picked했다고 가정 하면 테이블에있는 경우 하위 부분에 [1,5,17]있음을 알고 있습니다 9.
5 6 7 8
6 7 8 9
10 11 12 13 14 15 16
이것은 2 개의 직사각형을 제공합니다.
5 6 7 8 10 11 12 13 14 15 16
6 7 8 9
그래서 우리는 재귀 할 수 있습니다! 아마도 더 적은 요소를 가진 것으로 시작될 것입니다 (이 경우에는 우리를 죽입니다).
차원 중 하나가보다 작 으면 3대각 방법을 적용 할 수 없으며 이진 검색을 사용해야합니다. 여기서 의미는 다음과 같습니다.
- 에 바이너리 검색 적용
10 11 12 13 14 15 16, 찾을 수 없음 - 에 바이너리 검색 적용
5 6 7 8, 찾을 수 없음 - 에 바이너리 검색 적용
6 7 8 9, 찾을 수 없음
좋은 성능을 얻으려면 일반적인 모양에 따라 여러 경우를 구별하고 싶을 수 있기 때문에 까다 롭습니다 ....
3. 직사각형 검색, 잔인한 접근
정사각형을 다룬다면 훨씬 쉬울 것입니다 ... 그러니 그냥 정사각형으로합시다.
1 2 3 4 5 6 7 8
2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17
17 . . . . . . 17
. .
. .
. .
17 . . . . . . 17
이제 사각형이 생겼습니다.
물론 우리는 실제로 그러한 행을 생성하지 않을 것이며 단순히 에뮬레이트 할 수 있습니다.
def get(x,y):
if x < N and y < M: return table[x][y]
else: return table[N-1][M-1] # the max
그래서 그것은 더 많은 메모리를 차지하지 않고 정사각형처럼 작동합니다 (아마도 캐시에 따라 속도를 희생하여 ... 오 글쎄 : p)
편집하다:
나는 질문을 오해했다. 의견이 지적했듯이 이것은 더 제한된 경우에만 작동합니다.
행 우선 순서로 데이터를 저장하는 C와 같은 언어에서는 단순히 n * m 크기의 1D 배열로 취급하고 이진 검색을 사용합니다.
재귀 적 Divide & Conquer Solution이 있습니다. 한 단계에 대한 기본 아이디어는 다음과 같습니다. Left-Upper (LU)가 가장 작고 오른쪽 하단 (RB)이 가장 큰 번호라는 것을 알고 있으므로 주어진 No (N)는 N> = LU 및 N <=이어야합니다. RB
N == LU 및 N == RB :::: 요소가 발견되고 위치 / 인덱스를 반환하는 중단 N> = LU 및 N <= RB = FALSE 인 경우 No가 존재하지 않고 중단됩니다. N> = LU이고 N <= RB = TRUE이면 2D 배열을 2D 배열의 4 개의 동일한 부분으로 각각 논리적으로 나눕니다. 그런 다음 4 개의 하위 배열 모두에 동일한 algo 단계를 적용합니다.
내 알고리즘이 맞습니다. 친구 PC에 구현했습니다. 복잡성 : 각 4 개의 비교는 최악의 경우 총 요소 수를 4 분의 1로 추론하는 데 사용할 수 있습니다. 따라서 내 복잡성은 1 + 4 x lg (n) + 4가됩니다.하지만 실제로 O에서 작동 할 것으로 예상했습니다. (엔)
복잡도 계산 어딘가에 문제가 있다고 생각합니다. 그렇다면 수정하십시오 ..
최적의 솔루션은 최소한의 값이있는 왼쪽 상단 모서리에서 시작하는 것입니다. 주어진 요소의 값이> = 값인 요소를 칠 때까지 대각선으로 오른쪽 아래로 이동합니다. 요소의 값이 주어진 요소의 값과 같으면 found를 true로 반환합니다.
그렇지 않으면 여기에서 두 가지 방법으로 진행할 수 있습니다.
전략 1 :
- 열에서 위로 이동하고 끝에 도달 할 때까지 주어진 요소를 검색합니다. 발견되면 true로 반환
- 행에서 왼쪽으로 이동하고 끝에 도달 할 때까지 주어진 요소를 검색합니다. 발견되면 true로 반환
- 거짓으로 발견 된 반환
전략 2 : i는 행 인덱스를 나타내고 j는 우리가 멈춘 대각선 요소의 열 인덱스를 나타냅니다. (여기에 i = j, BTW가 있습니다). k = 1이라고합시다.
- ik> = 0이 될 때까지 아래 단계를 반복하십시오.
- a [ik] [j]가 주어진 요소와 같은지 검색합니다. 그렇다면 true로 반환됩니다.
- a [i] [jk]가 주어진 요소와 같은지 검색합니다. 그렇다면 true로 반환됩니다.
- 증가 k
12 4 5 6
2 3 5 78
4 6 8 9 10
5 8 9 10 11
public boolean searchSortedMatrix(int arr[][] , int key , int minX , int maxX , int minY , int maxY){
// base case for recursion
if(minX > maxX || minY > maxY)
return false ;
// early fails
// array not properly intialized
if(arr==null || arr.length==0)
return false ;
// arr[0][0]> key return false
if(arr[minX][minY]>key)
return false ;
// arr[maxX][maxY]<key return false
if(arr[maxX][maxY]<key)
return false ;
//int temp1 = minX ;
//int temp2 = minY ;
int midX = (minX+maxX)/2 ;
//if(temp1==midX){midX+=1 ;}
int midY = (minY+maxY)/2 ;
//if(temp2==midY){midY+=1 ;}
// arr[midX][midY] = key ? then value found
if(arr[midX][midY] == key)
return true ;
// alas ! i have to keep looking
// arr[midX][midY] < key ? search right quad and bottom matrix ;
if(arr[midX][midY] < key){
if( searchSortedMatrix(arr ,key , minX,maxX , midY+1 , maxY))
return true ;
// search bottom half of matrix
if( searchSortedMatrix(arr ,key , midX+1,maxX , minY , maxY))
return true ;
}
// arr[midX][midY] > key ? search left quad matrix ;
else {
return(searchSortedMatrix(arr , key , minX,midX-1,minY,midY-1));
}
return false ;
}
모든 문자를 2D list. 그런 다음 필요한 요소가 목록에 있으면 색인을 찾습니다.
존재하지 않으면 적절한 메시지를 인쇄하고 그렇지 않으면 행과 열을 다음과 같이 인쇄하십시오.
row = (index/total_columns) 과 column = (index%total_columns -1)
목록에서 이진 검색 시간 만 발생합니다.
수정 사항을 제안하십시오. :)
경우 O (M 로그 (N)) 용액을는 M × N 어레이에 대한 확인 인 -
template <size_t n>
struct MN * get(int a[][n], int k, int M, int N){
struct MN *result = new MN;
result->m = -1;
result->n = -1;
/* Do a binary search on each row since rows (and columns too) are sorted. */
for(int i = 0; i < M; i++){
int lo = 0; int hi = N - 1;
while(lo <= hi){
int mid = lo + (hi-lo)/2;
if(k < a[i][mid]) hi = mid - 1;
else if (k > a[i][mid]) lo = mid + 1;
else{
result->m = i;
result->n = mid;
return result;
}
}
}
return result;
}
이것이 작동하지 않거나 버그가 있으면 알려주십시오.
다음과 같이 정사각형 행렬이 주어집니다.
[abc] [데프] [ijk]
우리는 a <c, d <f, i <k를 알고 있습니다. 우리가 모르는 것은 d <c 또는 d> c 등입니다. 우리는 1 차원에서만 보증합니다.
끝 요소 (c, f, k)를 살펴보면 일종의 필터를 사용할 수 있습니다. is N <c? search () : next (). 따라서 행에 대해 n 개의 반복이 있으며 각 행은 이진 검색의 경우 O (log (n)) 또는 필터링 된 경우 O (1)를 사용합니다.
N = j 인 예를 들어 보겠습니다.
1) 행 1을 확인하십시오. j <c? (아니, 다음으로)
2) 행 2를 확인하십시오. j <f? (예, 빈 검색은 아무것도 얻지 못합니다)
3) 행 3을 확인하십시오. j <k? (예, 빈 검색이 찾습니다)
N = q로 다시 시도하십시오.
1) 행 1을 확인하십시오. q <c? (아니, 다음으로)
2) 행 2를 확인하십시오. q <f? (아니, 다음으로)
3) 행 3을 확인하십시오. q <k? (아니, 다음으로)
아마 더 나은 해결책이 있겠지만 이것은 설명하기 쉽습니다 .. :)
이것은 인터뷰 질문이므로 병렬 프로그래밍 및 Map-reduce 알고리즘에 대한 토론으로 이어질 것 같습니다 .
http://code.google.com/intl/de/edu/parallel/mapreduce-tutorial.html 참조
'programing tip' 카테고리의 다른 글
| 대규모 SQL 스크립트 실행 (GO 명령 사용) (0) | 2020.09.14 |
|---|---|
| "LINQ to Entities", "LINQ to SQL"및 "LINQ to Dataset"의 차이점은 무엇입니까? (0) | 2020.09.14 |
| 다음과 유사한 삼항 연산자? : (0) | 2020.09.14 |
| 데이터가 추가 될 때 div 끝으로 자동 스크롤하는 방법은 무엇입니까? (0) | 2020.09.14 |
| Haskell Prelude에서 'const'의 요점은 무엇입니까? (0) | 2020.09.14 |