순서가 있는 2차원 배열이 주어지고, 각 행은 왼쪽에서 오른쪽으로 증가하고, 각 열은 위에서 아래로 증가한다고 가정합니다. 함수를 완성하는 방법, 이러한 2차원 배열과 정수를 입력하고 정수 여부를 판단합니다. 이 2차원 배열에 있습니다.
4×4 순서의 2차원 배열을 가정합니다.
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
당신이 찾고 있는 숫자는 6입니다.
알고리즘의 핵심 아이디어는 왼쪽 상단의 숫자 9를 먼저 취하는 것입니다. 9는 6보다 크기 때문에 9보다 큰 숫자, 즉 네 번째 열을 제외하고 8을 취하면 됩니다. 세 번째 열을 제외하고 2를 취합니다. 6보다 작으면 2보다 작은 숫자, 즉 첫 번째 행을 제외할 수 있습니다. 같은 방법으로 4를 취하고 두 번째 행을 제외하고 7을 제외합니다. 두 번째 열은 4를 취하고, 세 번째 행을 제외하고, 6을 취하고, 같으면 true를 반환합니다.
여기서는 재귀를 사용하여 구현합니다. 코드는 다음과 같습니다.
다음과 같이 코드 코드를 복사합니다 .
공개 클래스 FindMatrixNumber {
개인 정적 FindMatrixNumber 인스턴스;
개인 정적 부울 발견 = false;
공개 정적 FindMatrixNumber getInstance() {
if (인스턴스 == null) {
인스턴스 = 새로운 FindMatrixNumber();
}
반환 인스턴스;
}
public static boolean find(int 행렬[][], int number) {
if (행렬 == null || 행렬.길이 == 0 || 행렬[0].길이 == 0) {
거짓을 반환;
} 또 다른 {
System.out.println("****찾기 시작****");
findMatrixNumber(행렬, 행렬.길이, 0, 행렬[0].길이,
숫자);
System.out.println("****찾기 끝*****");
}
반품을 찾았습니다.
}
private static void findMatrixNumber(int 행렬[][], int 행, int 행,
int 열, int 숫자) {
if (행 > 행 - 1)
반품;
int CornerNumber = 행렬[행][열 - 1];
System.out.println(cornerNumber);
if (코너번호 == 번호) {
발견 = 사실;
반품;
} else if (코너번호 < 번호) {
findMatrixNumber(행렬, 행, ++행, 열, 숫자);
} else if (코너번호 > 번호) {
findMatrixNumber(행렬, 행, 행, --columns, 숫자);
}
}
}
테스트 코드는 다음과 같습니다.
다음과 같이 코드 코드를 복사합니다 .
공개 클래스 TestFindMatrixNumber {
공개 정적 무효 메인(String[] args) {
int 행렬[][] = {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
System.out.println(FindMatrixNumber.find(행렬, 6));
}
}
테스트 코드를 실행한 결과는 다음과 같습니다.
다음과 같이 코드 코드를 복사합니다 .
****찾기 시작****
9
8
2
4
7
4
6
*****발견 종료*****
진실