Предположим, что дан упорядоченный двумерный массив, каждая строка увеличивается слева направо, а каждый столбец увеличивается сверху вниз. Как завершить функцию, ввести такой двумерный массив и целое число и определить, является ли оно целым числом. находится в этом двумерном массиве.
Предположим, что это упорядоченный двумерный массив размером 4 × 4:
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() {
если (экземпляр == ноль) {
экземпляр = новый FindMatrixNumber();
}
вернуть экземпляр;
}
public static boolean find(int матрица[][], int число) {
if (матрица == ноль || матрица.длина == 0 || матрица[0].длина == 0) {
вернуть ложь;
} еще {
System.out.println("****Начать поиск ****");
findMatrixNumber(матрица, матрица.длина, 0, матрица[0].длина,
число);
System.out.println("****Окончание поиска*****");
}
возврат найден;
}
Private static void findMatrixNumber(intматрица[][], int rows, int row,
int столбцы, int число) {
если (строка > строки - 1)
возвращаться;
int angularNumber = матрица [строка] [столбцы - 1];
System.out.println(номер угла);
if (cornerNumber == число) {
найдено = правда;
возвращаться;
} else if (cornerNumber <номер) {
findMatrixNumber(матрица, строки, ++строка, столбцы, число);
} еще если (cornerNumber > номер) {
findMatrixNumber(матрица, строки, строка, --столбцы, число);
}
}
}
Тестовый код:
Скопируйте код кода следующим образом:
общественный класс TestFindMatrixNumber {
public static void main(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
*****Конец поиска*****
истинный