2 차원 배열에서 비어 있지 않은 격자 셀 찾기

2 차원 정수 배열 (1000 x 1000)을 가지고 있습니다. 행렬이라고 부릅니다. 이 행렬의 각 셀에는 X 좌표와 Y 좌표가 있습니다 (이 예제에서는 각각 0에서 999까지입니다). 처음에는 모든 그리드 셀의 값이 0입니다. 프로그램 실행 중에 일부 매트릭스 셀은 <> 0으로 설정됩니다.2 차원 배열에서 비어 있지 않은 격자 셀 찾기

이제 X와 Y 값을 가져 와서 반환하는 빠른 함수 (알고리즘)가 필요합니다. 그 좌표의 행렬의 값 그러나 지정된 X/Y 위치의 행렬이 0 인 경우 알고리즘은 원래 X/Y 위치에 가능한 한 가깝게있는 행렬 내의 0이 아닌 값을 결정해야합니다.

...

어떤 아이디어 나 각 루프주기 오프셋 증가와 함께 원래의 X/Y 위치 주위에 루프에 대한 생각,하지만 난이 정말 빠른 알고리즘인지 확실하지 않다? Java 코드를 선호하지만 모든 의사 코드도 괜찮습니다.

미리 도움을 청하십시오! 좋은 점, Matthias

출처

2011-09-08 Matthias

어레이가 상대적으로 희박하고 테스트 수가 인서트 수에 비해 높으면 순진한 접근 방식이 오래 걸릴 수 있습니다.

대안은 쿼드 트리 또는 k-d 트리와 같은 공간 파티션 트리를 작성하는 것입니다. 가장 가까운 이웃 검색은 O (ln N) 삽입 시간의 비용으로 O (ln N)입니다.

출처

2011-09-08 16:22:34 Jimmy

매트릭스가 어떻게 보이는지에 대한 가정이 없다면 무작위 방법을 사용하여 [X, Y] 위치 근처의 모든 값을 살펴야합니다.

단지 설정 3 × 3의 중심에있는 [X, Y] 위치에 광장과 방금 스퀘어 5 * 5를 계속 아닌 값을 찾을 수없는 경우
주변 광장에 모든 값을 테스트 7x7 등을 찾을 때까지 큰 행렬의 경계를 처리해야합니다.

사이클, 색인 및 적절한 ifs와 관련된 작업입니다. :-) 정보가 없기 때문에 더 빠른 알고리즘은 없습니다.

출처

2011-09-08 16:12:25 TMS

0이 아닌 값을 포함 할 것으로 예상되는 행/열의 수에 따라 다릅니다. 1000x1000 격자에 < 개의 100 개의 위치가 채워질 것으로 예상되는 경우 값을 생성하는 동안 어떤 행 & 열의 정보를 저장해야합니다.

만약이 같은 그게 전부가 아니라 옵션 사용 뭔가를해야만 :

이

public void foo() { 
    int[][]matrix = new int[1000][1000]; 
    int x = 0,y = 0; 
    if(matrix[x][y] != 0) return; 
    int min = 0, max=0; 
    boolean cont = true; 
    foreverloop: 
    while(cont) { 
     min--;max++; 
     for(int ii = min; ii < max; ii++) { 
      // secure that min and max dont exeed matrix here. 
      cont = false; 
      int[] higherEnd = Arrays.copyOf(matrix[ii], max); 
      int[] trunk = Arrays.copyOf(higherEnd, higherEnd.length-min); 
      Arrays.sort(trunk); 
      if(trunk[trunk.length-1] != 0) { 
       // HIT! we search this distance but no further. 
       trunk = Arrays.copyOf(higherEnd, higherEnd.length-min); 
       int source = trunk.length; 
       for(int distance = 0; ;distance++) { 
        if(source-distance>0) { 
         if(trunk[source-distance] != 0) { 
          // SCORE! 
          scoreHit(x+ii,y+source-distance); 
          break foreverloop; 
         } 
        } 
        if(source+distance<trunk.length) { 
         if(trunk[source+distance] != 0) { 
          // SCORE! 
          scoreHit(x+ii,y+source-distance); 
          break foreverloop; 
         } 
        } 
       } 
      } 
     } 
    } 
} 

public void scoreHit(int x, int y) { 
    // there could be several in nearly the same distances 
}

당신은 이미 검색 영역을 필터링하여 해당을 최적화 할 수 있습니다,하지만 난 그는 X, Y에서 높은 거리에서 차이를 만들 것이라고 생각

출처

2011-09-08 16:37:40

2 차원 배열에서 비어 있지 않은 격자 셀 찾기

답변

관련 문제