Suponha que uma matriz bidimensional ordenada seja fornecida, cada linha aumente da esquerda para a direita e cada coluna aumente de cima para baixo. Como completar uma função, insira uma matriz bidimensional e um número inteiro e determine se o número inteiro. está nesta matriz bidimensional.
Suponha uma matriz bidimensional ordenada 4×4:
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
O número que você está procurando é 6.
A ideia central do algoritmo é primeiro pegar o número 9 no canto superior esquerdo. Como 9 é maior que 6, você pode excluir números maiores que 9, ou seja, a quarta coluna, e depois pegar 8. Da mesma forma, exclua a terceira coluna e depois pegue 2. Se for menor que 6, você pode excluir números menores que 2, ou seja, a primeira linha. Da mesma forma, pegue 4, exclua a segunda linha, pegue 7, exclua a. segunda coluna, pegue 4, exclua a terceira linha, pegue 6, igual, retorne verdadeiro.
Aqui usamos recursão para implementá-lo, o código é:
Copie o código do código da seguinte forma:
classe pública FindMatrixNumber {
instância privada estática de FindMatrixNumber;
booleano estático privado encontrado = falso;
public static FindMatrixNumber getInstance() {
if (instância == nulo) {
instância = new FindMatrixNumber();
}
instância de retorno;
}
public static boolean find(int matriz[][], int número) {
if (matriz == nulo || matriz.comprimento == 0 || matriz[0].comprimento == 0) {
retornar falso;
} outro {
System.out.println("****Começar a encontrar****");
findMatrixNumber(matriz, matriz.comprimento, 0, matriz[0].comprimento,
número);
System.out.println("****Fim da descoberta*****");
}
retorno encontrado;
}
private static void findMatrixNumber(int matriz[][], linhas int, linha int,
colunas int, número int) {
if (linha > linhas - 1)
retornar;
int cornerNumber = matriz[linha][colunas - 1];
System.out.println(cornerNumber);
if (cantoNumber == número) {
encontrado = verdadeiro;
retornar;
} else if (cornerNumber < número) {
findMatrixNumber(matriz, linhas, ++linha, colunas, número);
} else if (cornNumber > número) {
findMatrixNumber(matriz, linhas, linha, --colunas, número);
}
}
}
O código de teste é:
Copie o código do código da seguinte forma:
classe pública TestFindMatrixNumber {
public static void main(String[] args) {
matriz interna[][] = {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
System.out.println(FindMatrixNumber.find(matriz, 6));
}
}
O resultado da execução do código de teste é:
Copie o código do código da seguinte forma:
****Comece a encontrar****
9
8
2
4
7
4
6
*****Fim da descoberta*****
verdadeiro