赞
踩
提示:这里可以添加本文要记录的大概内容:
烦烦烦方法
例如:随着人工智能的不断发展,机器学习这门技术也越来越重要,很多人都开启了学习机器学习,本文就介绍了机器学习的基础内容。
提示:以下是本篇文章正文内容,下面案例可供参考
构建一个二维矩阵,在其中查找一个数是否存在,存在则输出 true ,不存在则输出 false 。
我们直接遍历整个二维矩阵,判断target是否出现即可
// 遍历整个矩阵,时间复杂度 O(mn)
public static boolean find1(int[][] matrix, int target) {
for (int[] row : matrix) {
for (int column : row) {
if (column == target) {
System.out.println("true");
return true;
}
}
}
System.out.println("false");
return false;
}
时间复杂度为 O(mn)
由于每一行都按升序排列,我们将二维的问题转化为一维数组,在每一行中通过二分查找法来寻找 target
// 遍历矩阵的每一行,并在每一行上使用二分查找进行查找 //时间复杂度 O(mlogn),二分查找每行时间复杂度O(logn),最多遍历m行 public static boolean find2(int[][] matrix, int target) { for (int[] row : matrix) { int index = search(row, target); if (index >= 0) { System.out.println("true"); return true; } } System.out.println("fase"); return false; } // 把当行进行二分查找 public static int search(int[] nums, int target) { int low = 0, high = nums.length - 1; while (low <= high) { int mid = (high - low) / 2 + low; int num = nums[mid]; if (num == target) { return mid; } else if (num > target) { high = mid - 1; } else { low = mid + 1; } } return -1; }
由于二分查找的时间复杂度为 O(logn) ,最多查找 m 行
时间复杂度O(mlogn)
我们可以从矩阵 matrix 的右上角 (0, n-1) 进行搜索。在每一步的搜索过程中,如果我们位于位置 (x, y),那么我们希望在以 matrix 的左下角为左下角、以 (x, y) 为右上角的矩阵中进行搜索,即行的范围为 [x, m - 1],列的范围为 [0, y]:
如果 [x, y] = matrix[x,y]=target,说明搜索完成;
如果 matrix[x,y] > target ,由于每一列的元素都是升序排列的,那么在当前的搜索矩阵中,所有位于第 y 列的元素都是严格大于 target 的,因此我们可以将它们全部忽略,即将 y 减少 1;
如果 matrix[x,y]<target,由于每一行的元素都是升序排列的,那么在当前的搜索矩阵中,所有位于第 x 行的元素都是严格小于 target 的,因此我们可以将它们全部忽略,即将 x 增加 1。
在搜索的过程中,如果我们超出了矩阵的边界,那么说明矩阵中不存在 target。
// Z字形查找,利用分治法,从右上角开始查找 // 当matrix[x][y]的值大于target时,将y-1;matrix[x][y]的值小于target时,将x+1 // 时间复杂度O(m+n),最多查找m行+n列 public static boolean find3(int[][] matrix, int target) { int m = matrix.length, n = matrix[0].length; int x = 0, y = n - 1; while (x <= m - 1 && y >= 0) { if (matrix[x][y] == target) { System.out.println("true"); return true; } if (matrix[x][y] > target) { --y; } if (matrix[x][y] < target) { ++x; } } System.out.println("false"); return false; }
同理,也可以从左下角向右上角查找
最多查找 m 行 + n 列
时间复杂度 O(mn)
本题的重点在于使用更加高效的方式进行求解,以上方法都应熟练掌握
本题还有一个应该注意的点时二维数组的输入,由于其中带有特殊字符 [] ,分割时应注意
代码及运行结果:
package matrix; import java.util.Scanner; public class Find_target { // 遍历整个矩阵,时间复杂度 O(mn) public static boolean find1(int[][] matrix, int target) { for (int[] row : matrix) { for (int column : row) { if (column == target) { System.out.println("true"); return true; } } } System.out.println("false"); return false; } // 遍历矩阵的每一行,并在每一行上使用二分查找进行查找,时间复杂度 O(mlogn),二分查找每行时间复杂度O(logn),最多遍历m行 public static boolean find2(int[][] matrix, int target) { for (int[] row : matrix) { int index = search(row, target); if (index >= 0) { System.out.println("true"); return true; } } System.out.println("false"); return false; } // 把当行进行二分查找 public static int search(int[] nums, int target) { int low = 0, high = nums.length - 1; while (low <= high) { int mid = (high - low) / 2 + low; int num = nums[mid]; if (num == target) { return mid; } else if (num > target) { high = mid - 1; } else { low = mid + 1; } } return -1; } // Z字形查找,利用分治法,从右上角开始查找 // 当matrix[x][y]的值大于target时,将y-1;matrix[x][y]的值小于target时,将x+1 // 时间复杂度O(m+n),最多查找m行+n列 public static boolean find3(int[][] matrix, int target) { int m = matrix.length, n = matrix[0].length; int x = 0, y = n - 1; while (x < m && y >= 0) { if (matrix[x][y] == target) { System.out.println("true"); return true; } if (matrix[x][y] > target) { --y; } if (matrix[x][y] < target) { ++x; } } System.out.println("false"); return false; } public static void main(String[] args) { int[][] nums = new int[5][5]; int i = 0, j = 0; System.out.print("nums="); Scanner scanner = new Scanner(System.in); String I = scanner.nextLine(); // 接受当前行输入的信息,并返回跳过的输入信息。即输入回车结束输入 String S = I.substring(I.indexOf("[[") + 2, I.lastIndexOf("]]")); /* * 此步是截取掉字符串中开头和结尾的两个中括号 substring(int beginIndex,int endIndex) * 该函数是截取字符串指定位置间的子字符串 该子字符串从指定的 beginIndex 处开始,直到索引 endIndex - 1 处的字符。 * indexOf(String str) 返回指定子字符串在此字符串中第一次出现处的索引。 lastIndexOf(String str) * 返回指定子字符串在此字符串中最右边出现处的索引。 注意:开头的中括号检索到的位置是第0位,我们要截去两个中括号,所以要加2。 */ String[] trans = S.split("\\],\\["); /* * 此步是将字符串中每行元素分开 split(String regex) 根据给定正则表达式的匹配拆分此字符串。 * 注意:因为用的是正则表达式,所以在使用特殊字符(如 * | [ ] 等)时要进行转义。即在“[”和“]”前加“//”。 */ for (i = 0; i < trans.length; i++) { String s = trans[i]; String[] snum = s.split(","); for (j = 0; j < snum.length; j++) { String string = snum[j]; nums[i][j] = Integer.parseInt(string); } } Scanner scanner2 = new Scanner(System.in); System.out.print("target="); int k = scanner2.nextInt(); scanner.close(); scanner2.close(); boolean r1 = find1(nums, k); boolean r2 = find2(nums, k); boolean r3 = find3(nums, k); } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。