网站接入查询,工业设计效果图,wordpress 首页显示分类文章,网址缩短链接在线工具题目#xff1a;
编写一个高效的算法来搜索矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性#xff1a;每行的元素从左到右升序排列。每列的元素从上到下升序排列。
实现#xff1a;
1. main方法
public static void main(String[] args) {int[][] matrix {{1…题目
编写一个高效的算法来搜索矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性每行的元素从左到右升序排列。每列的元素从上到下升序排列。
实现
1. main方法
public static void main(String[] args) {int[][] matrix {{1, 4, 7, 11, 15},{2, 5, 8, 12, 19},{3, 6, 9, 16, 22},{10, 13, 14, 17, 24},{18, 21, 23, 26, 30}};// 方式一暴力破解boolean b method1(matrix, 5);System.out.println(b);// 方式二二叉树原理查找method2(matrix, 5);
}2. 方式一暴力破解不推荐
/*** 方式一暴力破解* param matrix* param i*/private static boolean method1 ( int[][] matrix, int i){// 方式一暴力破解// 遍历矩阵找到对应元素即可,不推荐时间复杂度O(n^2)int row matrix.length;int col matrix[0].length;for (int j 0; j row; j) {for (int k 0; k col; k) {if (matrix[j][k] i) {System.out.println(way1: { j , k });return true;}}}return false;}
}3. 方式二 二叉树原理查找 /*** 方式二二叉树原理查找** param matrix* param target*/
private static boolean method2(int[][] matrix, int target) {// 方式二二叉树原理查找// 从左下角开始查找如果当前元素大于目标值则向上查找如果当前元素小于目标值则向右查找// 时间复杂度O(mn)int row matrix.length - 1; // 行int col 0; // 列while (col matrix[0].length row 0) {// 相等则返回if (matrix[row][col] target) {System.out.println(way2: { row , col });return true;} else if (matrix[row][col] target) { // 如果当前元素大于目标值则向上查找row--;} else if (matrix[row][col] target) { // 如果当前元素小于目标值则向右查找col;}}return false;
}
